8. Linked Lists

Linked lists are a sequential data structure that consist of an ordered set of Nodes in a chain like structure .

Linked lists are an ordered set of data elements, each containing a link to its successor (and sometimes its predecessor). The data elements are called Nodes. Each node contains a data element and a reference (or link) to the next node(s) in the sequence. Altogether, the data structure has a chain like structure 🔗 ⛓️.

Linked lists are one of the most fundamental data structures in computer science. They belong to a family of data structures that are based on the concept of Nodes (also known as vertices) and Links (also known as edges). Other members of this family include trees and graphs.

Where trees and graphs are hierarchical and non-linear data structures, linked lists are linear and sequential.

Fig. 8.1 Linked lists belong to a family of data structures that are based on the concept of nodes and connections. Nodes are depicted as circles, and connections are depicted as arrows between the circles.

Nodes are the building blocks of linked lists. These are themselves data structures. Each node contains atleast two components:

1. Data: The actual data that the node holds.

2. Pointers: References to adjacent nodes in the sequence. These references serve as the connections between nodes.

The first node in the linked list is called the head. The last node is called the tail. The tail node points to null or None to indicate the end of the list.

---

There are many types of linked lists, each with their own distinct structure of connections. The three most common types are:

Fig. 8.2 There are many types of linked lists, each with its own connection rules. The three most common types are Singly Linked Lists ➡️, Doubly Linked Lists ↔, and Circular Linked Lists 🔄, shown above.

1. Singly Linked Lists ➡️

Singly linked lists contain nodes that have a reference to the next node in the sequence. The last node in the sequence has a reference to None.

2. Doubly Linked Lists ↔

Doubly linked lists contain nodes that have references to both the next and previous nodes in the sequence. The first node in the sequence has a reference to None for the previous node, and the last node in the sequence has a reference to None for the next node.

3. Circular Linked Lists 🔄

Circular linked lists are a type of linked list where the last node in the sequence has a reference to the first node in the sequence, creating a circular structure.