How to implement custom Linked List in java
Linked list is inbuilt class of collection framework. But for understanding of linked list we can create our own linked list and write some common methods of linked list like add, remove, size etc.
List is sequential data structure, it is collection of nodes in linear fashion. One node have two fields first one is containing data or object and second one is reference to another node.
I have created inner Node class to represent node in custom linked list.
CustomLinkedList.java
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
139
140
141
142
143
| package com.javasuitor;
public class CustomLinkedList {
// Author : Ashok singh
// head points to start of linked list
Node head;
public CustomLinkedList() {
head = new Node(null);
}
public void addAtLast(Object object) {
Node newNode = new Node(object);
Node temp = head;
while (temp.getNext() != null) {
temp = temp.getNext();
}
// After loop temp will reach at end of list
temp.setNext(newNode);
}
public void traverseList() {
Node temp = head;
if (temp.getNext() == null) {
System.out.println("Underflow : List is empty");
System.exit(0);
}
while (temp.getNext() != null) {
temp = temp.getNext();
System.out.println(temp.getObject().toString());
}
}
public void addAtIndex(Object object, int index) {
Node temp = head;
Node temp2 = null;
Node newNode = new Node(object);
// check for empty list
if (temp.getNext() == null) {
temp.setNext(newNode);
return;
}
// Check for invalid index
if (index > size() - 1) {
System.out.println("Inserted Index does not exist in list");
System.exit(0);
}
for (int i = 0; i <= index; i++) {
temp2 = temp;
temp = temp.getNext();
}
temp2.setNext(newNode);
newNode.setNext(temp);
}
public int size() {
Node temp = head;
int count = 0;
while (temp.getNext() != null) {
count++;
temp = temp.getNext();
}
return count;
}
public void removeFromEnd(){
Node temp =head;
Node temp2=null;
// Check for Underflow
if(temp.getNext()==null){
System.out.println("UnderFlow : List is empty");
System.exit(0);
}
while(temp.getNext()!=null){
temp2=temp;
temp = temp.getNext();
}
// temp points to last node and temp2 points just before to temp.
temp2.setNext(null);
}
public void removeFromIndex(int index){
Node temp = head;
Node temp2 =null;
// Check for underflow
if(temp.getNext()==null){
System.out.println("Underflow : List is empty");
return;
}
// Check for invalid index
if(index > size()-1){
System.out.println("Wrong Input: Invalid index");
return;
}
for(int i=0;i<=index;i++){
temp2 = temp;
temp=temp.getNext();
}
temp2.setNext(temp.getNext());
temp.setNext(null);
}
private class Node {
Node next;
Object object;
public Node(Object object) {
// When Node will created its next pointer will be null, we will set
// it according to our requirement.
this.object = object;
this.next = null;
}
public Node getNext() {
return next;
}
public void setNext(Node next) {
this.next = next;
}
public Object getObject() {
return object;
}
public void setObject(Object object) {
this.object = object;
}
}
}
|
CustomLinkedListDemo.java
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
| package com.javasuitor;
public class CustomLinkedListDemo {
// Author : Ashok singh
public static void main(String[] args) {
CustomLinkedList customList = new CustomLinkedList();
customList.addAtLast(new Integer(10));
customList.addAtLast(new Integer(20));
customList.addAtLast(new Integer(30));
customList.addAtLast(new Integer(40));
System.out.println("Traverse Custom Linked List");
customList.traverseList();
// Add new object at existing index
// We consider as index starts from 0 as standard
customList.addAtIndex(25, 2);
System.out.println("Traverse List, after adding 25 at index 2");
customList.traverseList();
customList.removeFromEnd();
System.out.println("Traverse List, after last node removed");
customList.traverseList();
customList.removeFromIndex(1);
System.out.println("Traverse List, after 1st index node removed");
customList.traverseList();
System.out.println("Size of Custom Linked List "+customList.size());
}
}
|
Output :
Traverse Custom Linked List
10
20
30
40
Traverse List, after adding 25 at index 3
10
20
25
30
40
Traverse List, after last node removed
10
20
25
30
Traverse List, after 1st index node removed
10
25
30
Size of Custom Linked List 3
Diagrams help to understand linked list operation
 |
| Custom Linked List logical structure |
 |
| Add new element at the end of list |
 |
| Add new element at given index |
I hope you understand how to implement custom linked list in java. I feel happy to discuss. Please post your query in comment.
Happy learning.
No comments:
Post a Comment