Linked List, Stack and Queues
Linked Lists is another linear data structure which stores data in sequential order. But unlike Arrays which stores data in contiguous memory locations, the linked lists Instead of allocating sequential blocks of memory allow the blocks to be anywhere in the memory heap as long as we have pointers from one block to the next.
The linked list consists of lists of items called nodes. Each node has two parts: info and link. The info part stores the actual data and link part stores the address of next node. So every node except the last node contains the address of the next node. The last node has the value NULL in its link part.
Advantages of Linked Lists
- It does not have fixed size. So the number of items in the list is not fixed and can be increased as required.
- The deletion and insertion are easy.
- Accessing the elements is not as easy as compared to array.
Stack is a linear data structure. It is also called Last In First Out (LIFO) data structure. In this type of data structure, the element which is last added is first to be removed.
The stack supports two operations:
- Push: It adds element to the top of stack.
- Pop: It removes element from stack.
Stack resembles a stack of trays in a cafeteria, or stack of boxes. Only the top tray can be removed from the stack and it is the last one that was added to the stack. A tray can be removed only if there are some trays on the stack, and a tray can be added only if there is enough room to hold more trays.
Queue is another linear data structure in which the elements are added at one end, called the rear, and deleted from the other end, called the front. It is also called First In First Out (FIFO) data structure.
Waiting lines in supermarkets, banks, ticket counters, food counters are common examples of queues.