The linked list data structure is often used to implement other data structures.
A linked list is a sequence of nodes where each node stores its own data and a pointer (address) to the location of the next node.
One node links to another forming what can be thought of as a linked chain:
The last item in the list has a link to NULL, indicating the end of the chain.
Although a linked list is similar to an array, it is not restricted to a declared number of elements. Additionally, unlike an array which stores data contiguously in memory or on disk, a linked list can easily insert or remove elements without reallocation or reorganization of the entire structure because the data items need not be stored contiguously.
Linked List Drawbacks:
1) Random access is not allowed. We must access nodes sequentially starting from the first one. Therefore, we cannot do a binary search on a linked list.
2) Extra memory space for a link is required for each element of the list.
A stack is a simple data structure that adds and removes elements in a particular order.
Every time an element is added, it goes on the “top” of the stack. Only an element at the top of the stack can be removed, just like a stack of plates. This behavior is called LIFO (Last In, First Out).
Adding a new element onto the stack is called push.
Removing an element from the stack is called pop.
Stacks can be used to create undo-redo functionalities, parsing expressions (infix to postfix/prefix conversion), and much more.
A queue is a simple data structure that allows elements to be inserted from one end, called the rear (also called tail), and deleted from the other end, called the front (also called head).
This behavior is called FIFO (First in First Out).
The process of adding new elements into the queue is called enqueue.
The process of removal of an element from the queue is called dequeue.
Queues are used whenever we need to manage objects in order starting with the first one in.
Scenarios include printing documents on a printer, call center systems answering people on hold people, and so on.