Implementing a linked list in Java involves several steps. A linked list is a sequential data structure composed of elements called nodes. Each node contains data and a reference (or link) to the next node in the sequence.
First, you need to create a Node class. This class represents the nodes of the linked list. Each Node object should have two fields: one for the data it holds and another for a reference to the next Node object in the list.
Next, you create a LinkedList class, which is responsible for managing the nodes. This class should have a reference to the Node that marks the start of the list, commonly referred to as the head of the list.
Key operations you need to implement in the LinkedList class include:
- Insertion: You can insert a new node at the beginning, in the middle, or at the end of the list.
- Deletion: This involves removing a node from the list by updating the
nextreference of the previous node. - Search: This operation allows you to find a node in the list by traversing from the
headnode until the desired node is found. - Display: This is used for printing out the contents of the list from the
headto the end of the list.
What is a Linked List?
A linked list is a linear data structure that consists of a sequence of nodes, where each node stores a piece of data and a reference to the next node in the list. The reference to the next node is what makes the linked list "linked". In contrast to an array, where elements are stored in contiguous memory locations, a linked list does not require contiguous memory. Each node in a linked list is allocated dynamically, and it can be located anywhere in the memory.
In other words, a linked list can be visualized as a chain of nodes, where each node contains some data and a reference to the next node in the list. The first node in the list is called the head, and the last node is called the tail. The tail node's next reference is usually set to null to indicate the end of the list.
Types of Linked List
There are three types of linked lists: singly linked list, doubly linked list, and circular linked list. In a singly linked list, each node has a reference to the next node only. In a doubly linked list, each node has references to the next and previous nodes. In a circular linked list, the last node has a reference to the first node, creating a loop.
Singly Linked List
In a singly linked list, each node has a reference to the next node only. This means that we can traverse the list in only one direction - from the first node to the last node. The last node has a reference to null, indicating the end of the list.
Here's an example of a singly linked list:
1 -> 2 -> 3 -> 4 -> null
In this list, the first node has a value of 1 and a reference to the second node. The second node has a value of 2 and a reference to the third node, and so on. The last node has a value of 4 and a reference to null.
Doubly Linked List
In a doubly linked list, each node has references to both the next and previous nodes. This means that we can traverse the list in both directions - from the first node to the last node, and from the last node to the first node. The first node has a reference to null for its previous node, and the last node has a reference to null for its next node.
Here's an example of a doubly linked list:
null <- 1 <-> 2 <-> 3 <-> 4 -> null
In this list, the first node has a value of 1, a reference to null for its previous node, and a reference to the second node for its next node. The second node has a value of 2, a reference to the first node for its previous node, and a reference to the third node for its next node, and so on. The last node has a value of 4, a reference to the third node for its previous node, and a reference to null for its next node.
Circular Linked List
In a circular linked list, the last node has a reference to the first node, creating a loop. This means that we can traverse the list in both directions - from the first node to the last node, and from the last node to the first node. The last node has a reference to the first node for its next node, and the first node has a reference to the last node for its previous node.
Here's an example of a circular linked list:
1 -> 2 -> 3 -> 4 -> 1
In this list, the first node has a value of 1 and a reference to the second node for its next node. The second node has a value of 2 and a reference to the third node for its next node, and so on. The last node has a value of 4 and a reference to the first node for its next node. The first node has a reference to the last node for its previous node.
Implementing Linked List Java
To implement a linked list, we need to define two classes: a Node class that represents each node in the list, and a LinkedList class that represents the list itself.
Here's an example implementation of a singly linked list in Java:
public class Node {
int data;
Node next;
public Node(int data) {
this.data = data;
this.next = null;
}
}
public class LinkedList {
Node head;
public LinkedList() {
this.head = null;
}
public void insert(int data) {
Node newNode = new Node(data);
if (head == null) {
head = newNode;
} else {
Node current = head;
while (current.next != null) {
current = current.next;
}
current.next = newNode;
}
}
public void printList() {
Node current = head;
while (current != null) {
System.out.print(current.data + " ");
current = current.next;
}
System.out.println();
}
}
In this implementation, the Node class has two fields: data, which represents the data stored in the node, and next, which represents the reference to the next node in the list.
The LinkedList class has one field: head, which represents the first node in the list. It also has two methods: insert, which inserts a new node at the end of the list, and printList, which prints the data stored in each node in the list.
Let's see how we can use this implementation to create a list with the values 1, 2, 3, and 4, and print the list:
public class Main {
public static void main(String[] args) {
LinkedList myList = new LinkedList();
myList.insert(1);
myList.insert(2);
myList.insert(3);
myList.insert(4);
myList.printList();
}
}
Output:
1 2 3 4As we can see, we created a new LinkedList object called myList, inserted four values into the list using the insert method, and printed the list using the printList method. The output is 1 2 3 4, which represents the data stored in each node in the list.
Summary
The article provides a thorough exploration into the concept and implementation of Linked Lists in Java. It begins by explaining the fundamental structure of a linked list, a dynamic data structure that stores elements in non-contiguous memory locations. Each element, or 'node,' contains a reference to the next node, forming a chain-like structure. The article highlights the advantages of linked lists, such as their dynamic nature allowing efficient insertions and deletions, and their ability to use memory more flexibly.
Next, the article dives into the specifics of implementing a linked list in Java. It provides an overview of the 'Node' class, the backbone of any linked list, which typically consists of two parts: data and a reference (link) to the next node. It further elaborates on various operations such as insertion, deletion, and traversal, detailing the mechanisms behind each operation.
The article provides a comparison of singly linked lists and doubly linked lists, explaining the trade-offs between the two. It also describes the use of Java's built-in LinkedList class, which offers a wide range of methods for manipulating linked lists.
