Linked List (1)
• A linked list is a linear data structure that includes a series of connected
nodes. Each node stores the data and the address of the next node.
• It is a structure where each clue includes the information about the next
clue. For example,
• The address of the first node is called HEAD while the last node in the
linked list points to NULL.
• Linked lists can be singly, doubly, and circular linked.
Representation of Linked List
Each node consists of:
• A data item
• An address of another node
In Java, both the data item and the next node reference are wrapped in a class as follows:
class Node {
String data;
Node next;
Node(String d) { //class constructor
data = d;
next = null;
}
}
Linked List (2)
The power of a linked list comes from the ability to break the chain and
rejoin it. For example, if we wanted to put an element 4 between 1 and 2,
the steps would be:
Create a new node and allocate memory to it.
Add its data value as 4
Point its next pointer to the node containing 2 as the data value
Change the next pointer of "1" to the node we just created.
Doing something similar in an array would have required shifting the
positions of all the subsequent elements.
Linked List Utility
• Lists are one of the most popular and efficient data structures, with
implementation in every programming language.
• Linked lists are also a great way to learn how pointers work. By practicing
how to manipulate linked lists, you can prepare yourself to learn more
advanced data structures like graphs and trees.
Linked List Applications
1. Dynamic memory allocation
2. Implemented in stack and queue
3. In undo functionality of software
4. Hash tables, Graphs
Linked List Complexity
// Creating a Linked List in Java
class LinkedLst {
// Create a node
Node head;
static class Node {
String value;
Node next;
Node(String d) {
value = d;
next = null;
}
}
// Creating a Linked List in Java Cont’d
public static void main(String[] args) {
LinkedLst linkedList = new LinkedLst();
// Assign values
linkedList.head = new Node(“Gold”);
Node second = new Node(“Silver”);
Node third = new Node(“Diamond”);
// Connect nodes
linkedList.head.next = second;
second.next = third;
// printing node-value
while (linkedList.head != null) {
System.out.print(linkedList.head.value + “--> ");
linkedList.head = linkedList.head.next;
}
}
}
Linked List Operations: 1. Insertion
• The insertion operation adds a new element to the linked list.
• You can add elements to the beginning, end or after a given node in the linked
list.
Case 1: Insert at the beginning
1. Create a node and allocate memory for it through class declaration:
// Create a node
class Node {
int data;
Node next;
Node(int d) {
data = d;
next = null;
}
}
Linked List: Insert at the beginning
2. Store the new data (element)
3. Change next of new node to point to head
4. Change head to point to recently created node
As Follows:
// Insert at the beginning
public void insertAtBeginning(int new_data) {
// insert the data
Node new_node = new Node(new_data);
new_node.next = head;
head = new_node;
}
Linked List: Insert at the End
1. Allocate memory and store data for new node
2. Traverse to last node
3. Change next of last node to recently created node
As Follows:
public void insertAtEnd(int new_data) { //Insert at the end
Node new_node = new Node(new_data);
Node last = head;
while (last.next != null) {
last = last.next;
}
last.next = new_node;
return;
}
Linked List: Insert after a given Node
1. Allocate memory and store data for new node
2. Traverse to node just before the required position of new node
3. Change next pointers to include new node in between
As Follows:
// Insert after a given node
public void insertAfter(Node prev_node, int new_data) {
if (prev_node == null) {
System.out.println("The given previous node cannot be null");
return;
}
Node new_node = new Node(new_data);
new_node.next = prev_node.next;
prev_node.next = new_node;
}
Linked List Operations: 2. Deletion
• One can delete elements at the beginning, end or from a particular position in the linked
list.
Case 1: Delete at the beginning
Point head to the second node as follows:
Node temp = head;
head = temp.next;
Case 2: Delete from end
Traverse to the second last element
Change its next pointer to null
Node temp = head;
while(temp.next.next!=NULL){
temp = temp.next;
}
temp.next = NULL;
Linked List Operations: 2. Deletion Cont’d
Case 3: Delete from a given position
Change next pointers to exclude the node from the chain
Change next pointers to exclude the node from the chain
As follows:
for (int i = 0; temp != null && i < position - 1; i++) {
if (temp.next != null)
temp = temp.next;
}
}
Node next = temp.next.next;
Linked List Operations: 3. Searching for an Element
We can search an element on a linked list using a loop using the following
steps. We are finding item on a linked list:
1. Make head as the current node
2. Run a loop until the current node is NULL because the last element
points to NULL
3. In each iteration, check if the key of the node is equal to item. If the
key matches the item, return TRUE otherwise return FALSE
As follows:
Linked List Operations: 3. Searching Cont’d
// Search a node
boolean search(Node head, int key) {
Node current = head;
while (current != null) {
if (current.data == key)
return true;
current = current.next;
}
return false;
}
Linked List Operations: 4. Sorting Elements
To sort elements in a linked list follow the steps below:
1. Make the head as the current node and create another node index
for later use
2. If head is NULL return
3. Else, run a loop till the last node (ie., NULL)
4. In each iteration, follow step 5-6.
5. Store the next node of current in index
6. Check if the data of the current node is greater than the next node. If it is
greater, swap
As follows:
Linked List Operations: 4. Sorting Cont’d
// Sort the linked list
void sortLinkedList(Node head) {
Node current = head;
Node index = null;
int temp;
if (head == null) {
return;
} else {
while (current != null) {
// index points to the node next to current
index = current.next;
Linked List Operations: 4. Sorting Cont’d
while (index != null) {
if (current.data > index.data) {
temp = current.data;
current.data = index.data;
index.data = temp;
}
index = index.next;
}
current = current.next;
}
}
}
Linked List Operations: 5. Printing Elements
Printing elements of a liked list is done as follows:
// Print the linked list
public void printList() {
Node tnode = head;
while (tnode != null) {
System.out.print(tnode.data + " -->");
tnode = tnode.next;
}
Complete Java Implementation for Linked List
class LinkedList {
Node head;
// Create a node
class Node {
int data;
Node next;
Node(int d) {
data = d;
next = null;
}
}
Complete Java Implementation Cont’d
public void insertAtBeginning(int new_data) { // Insert at the beginning
Node new_node = new Node(new_data); // insert the data
new_node.next = head;
head = new_node;
}
public void insertAfter(Node prev_node, int new_data) { // Insert after a node
if (prev_node == null) {
System.out.println("The given previous node cannot be null");
return;
}
Node new_node = new Node(new_data);
new_node.next = prev_node.next;
prev_node.next = new_node;
}
Complete Java Implementation Cont’d
public void insertAtEnd(int new_data) { // Insert at the end
Node new_node = new Node(new_data);
if (head == null) {
head = new Node(new_data);
return;
}
new_node.next = null;
Node last = head;
while (last.next != null)
last = last.next;
last.next = new_node;
return;
}
Complete Java Implementation Cont’d
void deleteNode(int position) { // Delete a node
if (head == null)
return;
Node temp = head;
if (position == 0) {
head = temp.next;
return;
}
for (int i = 0; temp != null && i < position - 1; i++) // Find the key to be deleted
temp = temp.next;
if (temp == null || temp.next == null) // If the key is not present
return;
Node next = temp.next.next; // Remove the node
temp.next = next;
}
Complete Java Implementation Cont’d
// Search a node
boolean search(Node head, int key) {
Node current = head;
while (current != null) {
if (current.data == key)
return true;
current = current.next;
}
return false;
}
Complete Java Implementation Cont’d
void sortLinkedList(Node head) { // Sort the linked list
Node current = head;
Node index = null;
int temp;
if (head == null) {
return;
} else {
while (current != null) {
index = current.next; // index points to the node next to current
Complete Java Implementation Cont’d
while (index != null) {
if (current.data > index.data) {
temp = current.data;
current.data = index.data;
index.data = temp;
}
index = index.next;
}
current = current.next;
}
}
}
Complete Java Implementation Cont’d
// Print the linked list
public void printList() {
Node tnode = head;
while (tnode != null) {
System.out.print(tnode.data + " ");
tnode = tnode.next;
}
}
main file for Linked List Operations Cont’d
public static void main(String[] args) {
LinkedList llist = new LinkedList();
llist.insertAtEnd(1);
llist.insertAtBeginning(2);
llist.insertAtBeginning(3);
llist.insertAtEnd(4);
llist.insertAfter(llist.head.next, 5);
System.out.println("Linked list: ");
llist.printList();
System.out.println("\nAfter deleting an element: ");
llist.deleteNode(3);
llist.printList();
main file for Linked List Operations Cont’d
System.out.println();
int item_to_find = 3;
if (llist.search(llist.head, item_to_find))
System.out.println(item_to_find + " is found");
else
System.out.println(item_to_find + " is not found");
llist.sortLinkedList(llist.head);
System.out.println("\nSorted List: ");
llist.printList();
}
}
