Linked Lists

• A linked list, in simple terms, is a linear collection of data elements. These data elements are called nodes.
• Linked list is a data structure which in turn can be used to implement other data structures. Thus, it acts as a building block to implement data structures such as stacks, queues, and their variations.
• A linked list can be perceived as a train or a sequence of nodes in which each node contains one or more data fields and a pointer to the next node.

Simple Linked List

• We can see a linked list in which every node contains two parts, an integer and a pointer to the next node.
• The left part of the node which contains data may include a simple data type, an array, or a structure. The right part of the node contains a pointer to the next node (or address of the next node in sequence).
• The last node will have no next node connected to it, so it will store a special value called NULL.

Single Node in a Linked List

• Now we are going to discuss different types of linked lists and the operations that can be performed on these lists.

Linked Lists v/s Arrays

• Both arrays and linked lists are a linear collection of data elements. But unlike an array, a linked list does not store its nodes in consecutive memory locations.

• Another point of difference between an array and a linked list is that a linked list does not allow random access of data. Nodes in a linked list can be accessed only in a sequential manner. - But like an array, insertions and deletions can be done at any point in the list in a constant time.

• Another advantage of a linked list over an array is that we can add any number of elements in the list. This is not possible in case of an array.

  For example, if we declare an array as int marks[20], then the array can store a maximum of 20 data elements only. There is no such restriction in case of a linked list.

Different Types of Linked Lists

Singly Linked Lists

• A singly linked list is the simplest type of linked list in which every node contains some data and a pointer to the next node of the same data type. By saying that the node contains a pointer to the next node, we mean that the node stores the address of the next node in sequence. A singly linked list allows traversal of data only in one way.

Singly Linked List

Circular Linked Lists

• In a circular linked list, the last node contains a pointer to the first node of the list. We can have a circular singly linked list as well as a circular doubly linked list. While traversing a circular linked list, we can begin at any node and traverse the list in any direction, forward or backward, until we reach the same node where we started. Thus, a circular linked list has no beginning and no ending.

Circular Linked List

Doubly Linked Lists

• A doubly linked list or a two-way linked list is a more complex type of linked list which contains a pointer to the next as well as the previous node in the sequence. Therefore, it consists of three parts—data, a pointer to the next node, and a pointer to the previous node.

Doubly Linked List

Circular Doubly Linked Lists

• A circular doubly linked list or a circular two-way linked list is a more complex type of linked list which contains a pointer to the next as well as the previous node in the sequence.
• The difference between a doubly linked and a circular doubly linked list is same as that exists between a singly linked list and a circular linked list.
• The circular doubly linked list does not contain NULL in the previous field of the first node and the next field of the last node. Rather, the next field of the last node stores the address of the first node of the list, i.e., START. Similarly, the previous field of the first field stores the address of the last node.

Circular Doubly Linked List

Hop on to the next section to learn about the operations that can be performed on a linked list.