You just got an understanding of the basic concepts of Linked List and their variance. Now it’s time to implement a Linked List in Java to dive into the common Linked List operations that can be performed. Before you implement a Linked List in Java we remind you two important things about linked list:
- head points to the first node of the linked list.
- next pointer of last node is NULL.
Contents
hide
Implement a Linked List in Java
Simple Linked List
In this post, you will implement a linked list in java with three nodes. The simple linked list is designed like below
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
// Linked List Class class LinkedList { Node head; // head element /* Node Class */ class Node { int data; Node next; // Constructor and next is by default initialized as null Node(int d) {data = d; next = null; } } } |
How to traverse a linked list
It’s easy to traverse a linked list. You know that next points of last node is NULL. So you keep moving the next node when next points to NULL then you have reached the end of linked list.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 |
// A simple Java program to demonstrate a linked list class LinkedList { Node head; // head element /* Linked list Node*/ static class Node { int data; Node next; Node(int d){ data = d; next = null; } } /* traverse the created list and print the data of each node */ public void displayList() { Node n = head; while (n != null) { System.out.print(n.data + ","); n = n.next; } } /*create a simple linked list with 3 nodes*/ public static void main(String[] args) { /* Start with the empty list. */ LinkedList linkedlist = new LinkedList(); linkedlist.head = new Node(10); Node second = new Node(20); Node third = new Node(30); linkedlist.head.next = second; // Link first node with the second node second.next = third; // Link second node with the third node linkedlist.displayList(); } } |
Here is output of the above program
|
1 |
10,20,30, |
How to insert a node to linked list
In this post, methods to insert a new node in linked list are discussed. A node can be added in three ways:
- At the front of the linked list.
- After a given node.
- At the end of the linked list.
At the front of the linked list
|
1 2 3 4 5 6 7 8 9 10 11 12 |
/* Inserts a new Node at front of the list. */ public void push(int data) { // Create new Node Node newNode = new Node(data); // Make next of new Node as head newNode.next = head; // Move the head to point to new Node head = newNode; } |
Time complexity of push() is O(1) as it does constant amount of work.
Add a node after a given node
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
/* Inserts a new node after the given prevNode. */ public void insertAfter(Node prevNode, int newData) { //Don't insert if the given Node is null if (prevNode == null) { System.out.println("The given node cannot be null"); return; } // Allocate the Node and put in the new data Node newNode = new Node(newData); // Make next of new Node as next of prevNode newNode.next = prevNode.next; // make next of prevNode as newNode prevNode.next = newNode; } |
Time complexity of insertAfter() is O(1) too.
Add a node at the end
Here, you add a new node after the last node of linked list. You must traverse the list till end then change the next node of the last node to new node. So, time complexity of append is O(n) where n is the number of nodes in linked list.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
/* Appends a new node at the end. */ public void append(int newData) { //Allocate the Node put in the data Node newNode = new Node(newData); //If the list is empty, then make the new node as head if (head == null) { head = new Node(newData); return; } //Set next of it as null because this new node will be the last node newNode.next = null; // Traverse till the last node Node last = head; while (last.next != null) last= last.next; //Change the next of last node last.next = newNode; return; } |
Delete a node at a given position
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
/*Deletes the node at the given position */ void deleteNode(int position) { // If list is empty if (head == null) return; // Store head node Node temp = head; // remove head if (position == 0) { head = temp.next; return; } // Find previous node of the node to be deleted for (int i=0; temp!=null && i<position-1; i++) temp = temp.next; // If position is more than number of nodes if (temp == null || temp.next == null) return; // Store pointer to the next of node to be deleted Node next = temp.next.next; // Unlink the deleted node from list temp.next = next; } |
Completely implement a linked list in Java
Here is a simple program which implement a linked list in Java and its top 3 operations(traverse, add, delete)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 |
// A simple Java program to demonstrate a linked list class LinkedList { Node head; // head element /* Linked list Node*/ static class Node { int data; Node next; Node(int d){ data = d; next = null; } } /* traverse the created list and print the data of each node */ public void displayList() { Node n = head; while (n != null) { System.out.print(n.data + ","); n = n.next; } System.out.print("\n"); } /* Inserts a new Node at front of the list. */ public void push(int data) { // Create new Node Node newNode = new Node(data); // Make next of new Node as head newNode.next = head; // Move the head to point to new Node head = newNode; } /* Inserts a new node after the given prevNode. */ public void insertAfter(Node prevNode, int newData) { //Don't insert if the given Node is null if (prevNode == null) { System.out.println("The given node cannot be null"); return; } // Allocate the Node and put in the new data Node newNode = new Node(newData); // Make next of new Node as next of prevNode newNode.next = prevNode.next; // make next of prevNode as newNode prevNode.next = newNode; } /* Appends a new node at the end. */ public void append(int newData) { //Allocate the Node put in the data Node newNode = new Node(newData); //If the list is empty, then make the new node as head if (head == null) { head = new Node(newData); return; } //Set next of it as null because this new node will be the last node newNode.next = null; // Traverse till the last node Node last = head; while (last.next != null) last= last.next; //Change the next of last node last.next = newNode; return; } /*Deletes the node at the given position */ void deleteNode(int position) { // If list is empty if (head == null) return; // Store head node Node temp = head; // remove head if (position == 0) { head = temp.next; return; } // Find previous node of the node to be deleted for (int i=0; temp!=null && i<position-1; i++) temp = temp.next; // If position is more than number of nodes if (temp == null || temp.next == null) return; // Store pointer to the next of node to be deleted Node next = temp.next.next; // Unlink the deleted node from list temp.next = next; } /*create a simple linked list with 3 nodes*/ public static void main(String[] args) { /* Start with the empty list. */ LinkedList linkedlist = new LinkedList(); linkedlist.head = new Node(10); Node second = new Node(20); Node third = new Node(30); linkedlist.head.next = second; // Link first node with the second node second.next = third; // Link second node with the third node linkedlist.displayList(); //adding node linkedlist.push(50); //adding new node after element 10 linkedlist.insertAfter(linkedlist.head.next,60); linkedlist.append(70); linkedlist.displayList(); //deleting node linkedlist.deleteNode(4); linkedlist.displayList(); } } |
Here is output of the above program that implement a Linked List in Java
That’s all about the tutorial how to implement a Linked List in Java.
References
Linked List Data Structure in Java
Data Structures and Algorithms Tutorial in Java
