A linked list is a fundamental data structure in computer science that allows for efficient storage and retrieval of data. It is a linear data structure in which each element is connected to the next element through a pointer, forming a chain-like structure. In this article, we will explore how to create a linked list data structure in Java.
To begin with, we need to understand the basic components of a linked list. There are two main components – nodes and pointers. A node is an object that contains the data and a pointer to the next node. Pointers are used to connect the nodes and form the chain-like structure.
Let's start by creating a Node class in Java. This class will have two fields – data and next, which will be a pointer to the next node. The code for the Node class will look like this:
<code>
class Node {
int data;
Node next;
}
</code>
Next, we need to create a LinkedList class that will act as a wrapper for the nodes. This class will keep track of the head of the list and provide methods for adding, removing, and accessing elements in the list. The code for the LinkedList class will look like this:
<code>
class LinkedList {
Node head;
//Methods for adding, removing, and accessing elements will go here
}
</code>
Now, let's dive into the process of creating a linked list. We will start by creating an empty list by instantiating the LinkedList class.
<code>
LinkedList list = new LinkedList();
</code>
Next, we will add elements to the list. To add elements, we need to create nodes and link them together. Let's say we want to add the numbers 10, 20, 30, and 40 to the list. The process will be as follows:
<code>
//Creating nodes
Node node1 = new Node();
node1.data = 10;
Node node2 = new Node();
node2.data = 20;
Node node3 = new Node();
node3.data = 30;
Node node4 = new Node();
node4.data = 40;
//Linking nodes
list.head = node1;
node1.next = node2;
node2.next = node3;
node3.next = node4;
</code>
In the above code, we created four nodes and linked them together. We set the head of the list to point to the first node, and each node's next pointer is set to the next node in the list. This forms a chain-like structure, as shown below:
<code>
10 -> 20 -> 30 -> 40
</code>
We can now traverse the list and print out the elements using a while loop.
<code>
Node current = list.head;
while(current != null) {
System.out.println(current.data);
current = current.next;
}
</code>
This will print out the elements of the list in the order they were added – 10, 20, 30, and 40. We can also add elements at the beginning or end of the list by manipulating the pointers.
To add an element at the beginning of the list, we need to create a new node and set its next pointer to the current head of the list. Then, we set the head of the list to point to the new node.
<code>
Node newNode = new Node();
newNode.data = 5;
newNode.next = list.head;
list.head = newNode;
//New list after adding an element at the beginning
5 -> 10 -> 20 -> 30 -> 40
</code>
To add an element at the end of the list, we need to traverse the list until we reach the last node, then set its next pointer to point to the new node.
<code>
Node current = list.head;
while(current.next != null) {
current = current.next;
}
Node newNode = new Node();
newNode.data = 50;
current.next = newNode;
//New list after adding an element at the end
5 -> 10 -> 20 -> 30 -> 40 -> 50
</code>
Similarly, we can remove elements from the list by manipulating the pointers. To remove an element from the beginning, we set the head of the list to point to the second node.
<code>
list.head = list.head.next;
//New list after removing an element from the beginning
10 -> 20 -> 30 -> 40 -> 50
</code>
To remove an element from the end, we need to traverse the list until we reach the second last node and set its next pointer to null.
<code>
Node current = list.head;
while(current.next.next != null) {
current = current.next;
}
current.next = null;
//New list after removing an element from the end
10 -> 20 -> 30 -> 40
</code>
In conclusion, we have seen how to create a linked list data structure in Java. Linked lists are efficient for insertion and deletion operations, but they have a drawback of slower access time compared to arrays. However, they are an essential data structure to learn, and understanding how to create them in Java will be helpful in your programming journey.
