Node에 두개의 prev, next 포인터를 가지고 있는 리스트
1
2
3
4
5
6
7
8
public class Node {
public Node next;
public Node prev;
public int value;
public Node(int value) {
this.value = value;
}
}
DoublyLinkedList의 기본 구성
1
2
3
4
5
public class DoublyLinkedList {
private Node head;
private Node tail;
private int size;
}
구현 메소드 목록
1
2
3
4
5
6
7
8
9
10
- 구현 메소드 목록
- public DoublyLinkedList(int value);
- public void append(int value);
- public Node removeLast();
- public void prepend(int value);
- public Node removeFirst();
- public Node get(int index);
- public void set(int index, int value);
- public void insert(int index, int value);
- public Node remove(int index);
append(int value)
1
2
3
4
5
6
7
8
9
10
11
12
public void append(int value) {
Node newNode = new Node(value);
if (this.getSize() == 0) {
this.head = newNode;
} else {
this.tail.next = newNode;
newNode.prev = this.tail;
}
this.tail = newNode;
this.size++;
}
Node removeLast()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public Node removeLast() {
if (this.getSize() == 0) {
throw new NullPointerException("empty");
}
Node temp = this.tail;
if (this.getSize() == 1) {
this.head = null;
this.tail = null;
} else {
this.tail = this.tail.prev;
this.tail.next = null;
temp.prev = null; // 참조를 끊어낸다.
}
this.size--;
return temp;
}
void prepend(int value)
1
2
3
4
5
6
7
8
9
10
11
12
public void prepend(int value) {
Node newNode = new Node(value);
if (this.getSize() == 0) {
this.head = newNode;
this.tail = newNode;
} else {
newNode.next = this.head;
this.head.prev = newNode;
this.head = newNode;
}
this.size++;
}
Node removeFirst()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public Node removeFirst() {
Node temp = this.head;
if (this.getSize() == 0) {
throw new NullPointerException("empty");
} else if (this.getSize() == 1) {
this.head = null;
this.tail = null;
} else {
this.head = temp.next;
temp.next = null;
temp.prev = null;
}
this.size--;
return temp;
}
Node get(int index)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public Node get(int index) {
if (this.getSize() <= index || index < 0) {
return null;
}
Node temp = this.head;
if (index < this.getSize() / 2) {
for (int i = 0; i < index; i++) {
temp = temp.next;
}
} else {
temp = this.tail;
for (int i = this.getSize() - 1; i > index; i--) { // ToDO
temp = temp.prev;
}
}
return temp;
}
void set(int index, int value)
1
2
3
4
public void set(int index, int value) {
Node node = this.get(index);
node.value = value;
}
void insert(int index, int value)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public void insert(int index, int value) {
if (index == 0) {
prepend(value);
} else if (this.getSize() == index) {
append(value);
} else {
Node newNode = new Node(value);
Node temp = this.get(index);
newNode.prev = temp.prev;
temp.prev.next = newNode;
newNode.next = temp;
temp.prev = newNode;
this.size++;
}
}
Node remove(int index)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public Node remove(int index) {
Node temp = this.get(index);
if (index >= this.getSize() || index < 0) {
return null;
} else if (this.getSize() - 1 == index) {
removeLast();
} else if (index == 0) {
removeFirst();
} else {
Node before = temp.prev;
Node after = temp.next;
before.next = after;
after.prev = before;
temp.prev = null;
temp.next = null;
this.size--;
}
return temp;
}