Lists as a data structure
Array and linked lists are very similar to each other, yet very different.
Both can be used to store string, int, etc. However, in an array, the elements are indexed. So if you wanna get to the fourth element, you can *boom* do that in an instant. In a linked list, you have to start with the head (first element) and work your way through one by one, until you reach the fourth element. This makes linked lists significantly slower in comparison because it takes linear time (Big oh is linearly dependent on the number of elements in your input).
Then why would someone ever use a linked list over an array?
Well, insertions and deletions can be very quick. If you want to add or delete an element from the beginning of the linked list, that can be done in constant time. Constant time is super desirable since it works well with scaling. For eg., if you have a very large linked list and wish to delete the first 3000 elements, that will take only as much time as it would, to delete the first element from a two-element list.
Of course, if you want this operation to be done at the end of the linked list, that might require all the way walking through the list. And this increases with the list size — so not very scalable.
Linked lists can be singly linked (i.e. in one direction) or doubly linked (i.e. in both directions).
Linked lists can also be circularly linked, meaning, the first element is linked to the last element.
How do you pre-pend elements into a linked list?
Well, all the elements in a list are linked to the same head. But if we change the head in one place, we need all elements to know that. Linked lists are a workaround for this, as all elements do not have access to the head. So prepending becomes simple. Also, if the head is null, you can just create the head.
Prepending an element is super simple in a linked list because you just create an element → prepend it to the existing head → declare the new element as the head.
Stack vs. Queue
These two data structures differ in terms of how the item to be removed is chosen. Stacks follow the last in first out method, or LIFO, which is relatively easy to implement. The operation performed is called ‘push and pop’. This is because the same end is used for adding and deleting items, so only one pointer has to be used.
Queues follow the first in first out method or FIFO. The operation is called enqueue and dequeue. This uses two pointers since the access has to remain from both ends of the structure. This is comparatively complex to implement but also allows variations like circular queue, priority queue, doubly ended queue.
