Computer Science > Data Structures > Linked Lists
Linked Lists
A linked list is a fundamental data structure in computer science that consists of a sequence of elements, each of which contains a reference (or link) to the next element in the sequence. Unlike arrays, linked lists do not store their elements in contiguous memory locations. Instead, each element, or node, in a linked list is typically composed of two parts: the data it holds and a pointer (or reference) to the next node in the sequence.
Structure and Components
A basic linked list node can be defined as follows:
\[
\text{struct Node} \{
\text{int data}; \\
\text{struct Node* next}; \\
\};
\]
- Node: The building block of a linked list. Each node contains data and a reference to the next node.
- Head: A reference to the first node in the list. If the list is empty, the head is null.
- Tail: The last node in the list, which typically points to null, indicating the end of the list.
Types of Linked Lists
- Singly Linked List: Each node contains a single link to the next node, and traversal is typically unidirectional, moving from the head towards the tail.
\[
\begin{tabular}{|c|c|}
\hline
\text{Data} & \text{Next} \\
\hline
A & \rightarrow B \\
\hline
B & \rightarrow C \\
\hline
C & \rightarrow \text{null} \\
\hline
\end{tabular}
\]
- Doubly Linked List: Each node contains two links, one to the next node and one to the previous node, facilitating bidirectional traversal.
\[
\begin{tabular}{|c|cc|}
\hline
\text{Prev} & \text{Data} & \text{Next} \\
\hline
\text{null} & A & \rightarrow B \\
\hline
\leftarrow A & B & \rightarrow C \\
\hline
\leftarrow B & C & \text{null} \\
\hline
\end{tabular}
\]
- Circular Linked List: In this variant, the last node points back to the first node, forming a loop.
- Singly Circular Linked List: Only a single link exists pointing to the next node.
- Doubly Circular Linked List: Two links exist, pointing to both the next and previous nodes.
Operations
- Insertion: Adding a new node to a linked list can occur at the beginning, at the end, or at a specified position.
\[
\text{Insert At Head:}
\]
\(
\text{new node} \rightarrow \text{next} = \text{head}; \\
\text{head} = \text{new node};
\)
\(
\text{Insert At Tail:}
\)
\[
\text{tail} \rightarrow \text{next} = \text{new node}; \\
\text{new node} \rightarrow \text{next} = \text{null}; \\
\text{tail} = \text{new node};
\]
- Deletion: Removing a node from a linked list requires updating the references of the preceding nodes.
\[
\text{Delete Node After Given Node:}
\]
\[
\text{node} \rightarrow \text{next} = \text{node} \rightarrow \text{next} \rightarrow \text{next};
\]
- Traversal: Traversing through a linked list involves starting from the head and following the links until the desired node is found or until reaching the end of the list.
Advantages and Disadvantages
Advantages:
- Dynamic size: Linked lists can efficiently grow and shrink during runtime.
- Ease of Insertions/Deletions: Insertions and deletions are simpler and do not require shifting elements as in arrays.
Disadvantages:
- Memory Usage: Linked lists require extra memory for storing pointers.
- Sequential Access: To access a node, traversal through nodes is required, which can be less efficient compared to array indexing.
Linked lists are an essential data structure for understanding more complex structures and algorithms, providing foundational knowledge that underpins many areas of computer science.