A linked list is a popular data structure used in computer science for storing and manipulating a collection of elements. It consists of a sequence of nodes, where each node contains both data and a reference (or link) to the next node in the sequence. Unlike arrays, linked lists do not require contiguous memory allocation, making them more flexible for dynamic data storage.
What is a Node?
A node is the basic building block of a linked list. It contains two parts: the data part, which holds the value or information, and the link part, which points to the next node in the sequence. Each node is connected to its adjacent nodes through these links.
Types of Linked Lists
There are several types of linked lists depending on their structure:
Singly Linked List
In a singly linked list, each node has only one link pointing to the next node. The last node’s link points to null, indicating the end of the list.
Doubly Linked List
In a doubly linked list, each node has two links: one pointing to the previous node and another pointing to the next node. This allows for bi-directional traversal within the list.
Circular Linked List
In a circular linked list, the last node’s link points back to the first node instead of null, creating a circular structure. This enables seamless traversal from any point in the list.
Example:
Let’s consider an example to better understand how a singly linked list works. We will create a linked list containing three nodes: Node A with value 10, Node B with value 20, and Node C with value 30.
<pre><code class="language-java">
class LinkedListNode {
int data;
LinkedListNode next;
}
public class LinkedListExample {
public static void main(String[] args) {
LinkedListNode a = new LinkedListNode();
LinkedListNode b = new LinkedListNode();
LinkedListNode c = new LinkedListNode();
a.data = 10;
b.data = 20;
c.data = 30;
a.next = b;
b.next = c;
// Traversing the linked list
LinkedListNode currentNode = a;
while (currentNode != null) {
System.out.print(currentNode.data + " ");
currentNode = currentNode.next;
}
}
}
</code></pre>
In the example above, we create three node objects: ‘a’, ‘b’, and ‘c’. Each node is assigned a value using the ‘data’ field.
The ‘next’ field is used to establish the link between nodes. The link of node ‘a’ points to node ‘b’, and the link of node ‘b’ points to node ‘c’. Finally, we traverse the linked list starting from node ‘a’ and print the values.
Advantages of Linked Lists
- Dynamic Size: Linked lists can grow or shrink dynamically, unlike arrays that have a fixed size.
- Efficient Insertion/Deletion: Insertion or deletion of elements at any position in the linked list can be done more efficiently compared to arrays.
- Memory Flexibility: Linked lists do not require contiguous memory allocation, allowing for efficient memory utilization.
Disadvantages of Linked Lists
- Inefficient Random Access: Unlike arrays, accessing elements at random positions in a linked list is inefficient as it requires traversing from the beginning of the list.
- Extra Memory Overhead: Linked lists require additional memory for storing the links between nodes, increasing memory overhead compared to arrays.
In conclusion, a linked list is a versatile data structure that provides flexibility and efficiency for dynamic data storage. Understanding its various types and implementing them in applications can greatly enhance your programming skills.