-
Notifications
You must be signed in to change notification settings - Fork 4
/
DoublyLinkedList.java
87 lines (77 loc) · 1.72 KB
/
DoublyLinkedList.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
package custom.linked.list;
import lombok.Getter;
import lombok.Setter;
@Getter @Setter
public class DoublyLinkedList<T> {
Node<T> start;
public void addFirst(T elt){
Node<T> newNode = new Node<T>(elt);
newNode.prev = null;
newNode.next = start;
if(start!=null) // If this is not the first node to be inserted.
start.prev = newNode;
start = newNode;
}
public void addLast(T elt){
Node<T> newNode = new Node<T>(elt);
newNode.next = null;
Node<T> i=start;
for(; i.next!=null; i=i.next);
i.next = newNode;
newNode.prev = i;
}
public void add(T elt, int index){
if(index==0)
addFirst(elt);
else{
Node<T> node=start, backNode=start;
for(int i=1; i<=index && node!=null; i++){
backNode = node;
node = node.next;
}
if(node!=null){
Node<T> newNode = new Node<T>(elt);
newNode.prev = backNode;
newNode.next = node;
backNode.next = newNode;
node.prev = newNode;
} else{
addLast(elt);
}
}
}
public boolean delete(T elt){
if(start.getValue().equals(elt)){
start = start.next;
return true;
}
Node<T> i=start, backNode=start;
for(; i!=null; i=i.next){
if(i.value.equals(elt)){
backNode.next = i.next;
if(i.next!=null) i.next.prev = backNode; // If it's not the last node.
return true;
}
backNode = i;
}
return false;
}
@Override
public String toString() {
String asStr="start";
for(Node<T> i=start; i!=null; i=i.next){
asStr = asStr + " <--> " + i.getValue();
}
return asStr;
}
@Getter @Setter
static class Node<T>{
T value;
Node<T> prev;
Node<T> next;
Node(){}
Node(T value){
this.value = value;
}
}
}