-
Notifications
You must be signed in to change notification settings - Fork 0
/
LinkedList.java
127 lines (97 loc) · 3.97 KB
/
LinkedList.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
/**
*
* @author swapnil
*/
public class LinkedList {
private Node head; // Head of the list
// Insert function
boolean insert(String key, long value) {
boolean result = false;
// If the list is empty
if (head == null) {
// Create a new Node
Node newNode = new Node(key, value);
head = newNode; // Make head point to the newly created node
result = true; // Insertion happened successfully
} else {
// Check if the given key already exists or not
if (find(key) == -1) {
// If the key doesn't exist in the list insert the key
// Initialize nodePtr to head
Node nodePtr = head;
// Advance all the way to the last node of the list
while (nodePtr.next != null) {
nodePtr = nodePtr.next;
} // end of while
// Create new Node and make the last node point to it
Node newNode = new Node(key, value);
nodePtr.next = newNode;
result = true; // Insertion happened successfully
} // end of inner if
} // end of outer if
return result;
} // end of insert
// Delete function to remove the node in the list
boolean delete(String ky) {
boolean result = false;
// If the list is empty return false
if (head == null) {
return result;
} else if (find(ky) != -1) { // Check whether the given key is in the list or not
// If it is in the list
// Check if head is pointing to it or not
if (head.key.equals(ky)) {
// If head is pointing to it
// make head point to next node
head = head.next;
} else {
// If head is not pointing to it
// Find the key and remove it from the chain
Node prevNode = head;
while (prevNode.next != null) {
// Check if the next node is the node that we are looking for
if (prevNode.next.key.equals(ky)) {
// If next node is the one that we are looking
// Assign new value for next
prevNode.next = (prevNode.next).next;
} else {
// If it isn't the one that we are looking for
// Advance prevNode to next node
prevNode = prevNode.next;
} // end for inner if
} // end for while
} // end for outer if
result = true; // If everything goes right the node is deleted
} // end for outer if
return result; // Returning the result
} // end of delete
// Find function to search a key in the list
long find(String ky) {
long result = -1; // Initialize the result to -1 assuming the key is not found yet
Node nodePtr = head;
// If the list is empty the key is not in there
if (head == null) {
return result; // Returning the result
}
// While loop to transverse through the list and search if the key is present
// Condition: Execute till nodePtr is not pointing to the key that
// we are looking for and next node is not null
while (!nodePtr.key.equals(ky) && nodePtr.next != null) {
nodePtr = nodePtr.next;
} // end of while
// If nodePtr is pointing to the key that we are looking for
if (nodePtr.key.equals(ky)) {
// Returning the value of the key
result = nodePtr.value;
} // end of if
return result; // Returning value of the key
} // end of find
// Clear function to clear the list
void clear() {
head = null;
} // end of clear
// Constructor
LinkedList() {
head = null;
}
}