A linked list is a list of connected nodes. Each node stores the value and address of the next or the previous node. Since the address is stored in the node, linked lists can be dynamically allocated. Linked lists are used in implementing dynamic arrays, stacks, and queues. However, they consume extra memory for storing the address of the next node. These sequential lists are very cumbersome for traversing longer lists.
Array vs Linked List
Compared to an array, a linked list can be easily traversed if the list size is smaller. Unlike arrays linked list items cannot be randomly accessed. Lists store the address of the next node, hence consume more space. Below picture shows how a linked list can store items anywhere and accessed by the address sequentially. The address can be used to locate the element. This makes insertion, deleting or updating operations in a linked list faster.
Arrays are stored in memory sequentially and accessed using the array index. Hence, arrays take a longer time for insertion, deleting or updating. Types of Linked Lists
Linked lists are of 3 main types:
A Singly linked list
They contain a list of nodes that have a value and address to the next node. The last node’s address is always null. Below illustration shows that a singly linked list can traverse forward only. Stacks, queues and dynamic arrays are some implementation areas where singly linked lists are used. They are best suited for smaller forward traversals and when the address to the element is unknown.
A Doubly linked list
A doubly linked list has 3 parts – node value, address to the next node and address to the previous node. The first node’s address to the previous element and the last node’s address to the next node will always be null. A doubly linked list can hence traverse both forward and backward. We use a doubly linked list to navigate either forward or backward direction, when using an array or other data structures. However, both next and previous address needs to be stored in the node and hence consumes more memory.
A Circular linked list
When the last node’s address points to the first node, the linked list is called a circular linked list. A circular linked list can be singly or doubly linked.
Below is an example of a singly linked circular list.
A doubly linked circular linked list is just like the doubly linked list except that the last node’s next pointer stores the address of the first node and the first node’s previous pointer stores the address of the last node. The operating system’s task scheduler, circular queues and multi-player games are great real-world examples of a circular linked list.
Learn more about Link Lists and other Data Structures and Algorithms Interview Questions from our books at Vibrant Publishers