What Is Singly Linked List in Data Structure Example?
A singly linked list is a type of data structure commonly used in computer science and programming. It consists of a sequence of nodes, where each node contains two parts: data and a reference to the next node in the sequence.
Structure of a Singly Linked List
In a singly linked list, each node has two components:
- Data: This component holds the actual value or data that we want to store in the linked list.
- Next: This component is a reference or pointer to the next node in the sequence. It allows us to traverse through the list from one node to another.
The first node in the list is called the head, and it is used as a starting point for accessing or manipulating the entire linked list. The last node in the list, which does not have a reference to any other node, is called the tail.
An Example:
Let’s take an example to understand how a singly linked list works. Suppose we want to create a linked list that stores integers.
“`
class Node {
int data;
Node next;
public Node(int data) {
this.data = data;
this.next = null;
}
}
“`
In this example, we have defined a class called `Node` that represents each individual node in our linked list. The `Node` class has two components: `data`, which stores an integer value, and `next`, which points to the next `Node` object.
“`
Node head = new Node(5);
Node second = new Node(10);
Node third = new Node(15);
head.next = second;
second.next = third;
“`
In the above code snippet, we have created three nodes: `head`, `second`, and `third`. We then set the `next` reference of each node to the next node in the sequence.
Traversing a Singly Linked List
To traverse a singly linked list, we start from the head node and follow the `next` references until we reach the end of the list. Here’s an example:
“`
Node currentNode = head;
while (currentNode != null) {
System.out.print(currentNode.data + ” “);
currentNode = currentNode.next;
}
“`
In this code snippet, we initialize a variable called `currentNode` with the value of `head`. We then iterate through the linked list using a while loop. Inside the loop, we print the data value of each node and update `currentNode` to point to the next node in the sequence.
Advantages of Singly Linked List
- Singly linked lists are relatively simple to implement and understand.
- Insertion and deletion operations can be performed efficiently in a singly linked list.
- Singly linked lists use memory efficiently as they only require additional space for storing references.
Disadvantages of Singly Linked List
- Random access is not possible in a singly linked list. To access an element at a particular position, we need to traverse from the beginning of the list.
- Searching for an element in a singly linked list has a time complexity of O(n), where n is the number of elements in the list.
- Deleting a node from a singly linked list requires updating the `next` reference of the previous node, which can be time-consuming in some cases.
In conclusion, a singly linked list is a fundamental data structure that allows us to efficiently store and manipulate data elements. It provides flexibility in terms of insertion and deletion operations, but it sacrifices random access and search efficiency. Understanding the concepts behind a singly linked list is crucial for any programmer or computer science student.