자바 예제로 설명하는 더블 링크드 리스트(Singly Linked List)
더블 링크드 리스트란?
우선 시작하기 전에 잠시 싱글 링크드 리스트(단수 링크드 리스트) 이야기를 조금 해보자. 싱글 링크드 리스트에서 각각의 노드는 다음 노드의 주소만을 가지고 있기 때문에, 꼬리 노드, 즉 가장 마지막 노드를 제거하기 위해서 필수적으로 그 앞의 모든 노드들을 거쳐(Traverse)야 했다. 결국 싱글 링크드 리스트에서 removeTail 메소드는 O(n)의 효율성을 가질 수 밖에 없었다. 그렇니 잠시 이 구조를 어떻게 더 좋게 만들지 생각해 보자. 만약 각각의 노드가 자신의 전 노드(Predecessor Node) 와 다음 노드(Successor Node)의 주소를 모두 가지고 있다면 약간 더 많은 메모리를 쓰게 되지만 기능적으로는 더 효율적이지 않을까? 이게 바로 더블 링크드 리스트의 컨셉이다. 각각의 노드가 자신의 Predecessor Node와 Successor Node를 모두 참조한다는 것을 제외하고는 모든게 싱글 링크드 리스트(Singly Linked List)와 같다. |
| 더블 링크드 리스트 예제 |
우리가 노드에 인터져만을 저장한다고 할 때 노드는 아래와 같이 구현된다.
아래는 자바 예제이다.
public class Node {
public class Node {
private int data;
private Node predecessor, successor;
public Node(int data) {
this.data = data;
}
public Node(int data, Node predecessor, Node successor) {
this.data = data;
this.predecessor = predecessor;
this.successor = successor;
}
public int getData() {
return data;
}
public void setData(int data) {
this.data = data;
}
public Node getPredecessor() {
return predecessor;
}
public void setPredecessor(Node predecessor) {
this.predecessor = predecessor;
}
public Node getSuccessor() {
return successor;
}
public void setSuccessor(Node successor) {
this.successor = successor;
}
}
아래 표는 더블 링크드 리스트의 메소드들의 Big O 복잡도이다
Operation 이름 Big O 복잡도 addHead(int t) O(1) addTail(int t) O(1) search(int t) O(n) remove(int t) O(n) removeHead() O(1) removeTail() O(1) clear() O(1) isEmpty() O(1)
void addHead(int t)
 |
| 더블 링크드 리스트 addHead 메소드 |
- head 인스턴스를 통해 첫번째 노드를 엑세스 한다.
- 새 노드의 successorNode 필드가 head instance 가 참조하는 첫번째 노드를 참조하도록 하게 한다
- head 인스턴스와 첫번째 노드간의 링크를 부수고 head 인스턴스가 새 노드를 참조게 한다.
public void addhead(int t) {
Node newNode = new Node(t);
if (isEmpty()) {
head = newNode;
tail = head;
} else {
newNode.setSuccessor(head);
head = newNode;
}
}
우선 파라미터로 받은 인터져 t 를 이용하여 새로운 노드 newNode 인스턴스를 생성한다. 그리고 리스트가 empty 상태인지 아닌지 확인한다. 만약 리스트가 empty 상태라면 우리는 head와 tail 인스턴스가 새로운 노드 newNode를 참조게 한다.
만약 리스트가 empty 상태가 아니라면, newNode의 successor 필드에 head 인스턴스가 참조하고 있는 첫번째 노드를 어싸인해준다. 그리고 head 인스턴스가 새 노드를 참조하게 만든다
void addTail(int t)
 |
| 더블 링크드 리스트 addTail 메소드 |
이 메소드는 주어진 인터져 t 로 만든 새로운 노드를 리스트의 가장 마지막 위치에 삽입한다
- tail 인스턴스를 통해 가장 마지막 노드에 엑세스 한후, 가장 마지막 노드의 successor 필드가 새로운 노드를 참조하게 한다
- 새 노드의 predecessor 필드가 마지막 노드를 참조하게 한다
- tail 인스턴스가 새로운 노드를 참조하게 만든다.
아래는 자바로 구현된 addTail 메소드 이다.
public void addTail(int t){
Node newNode = new Node(t);
if(isEmpty()){
head = newNode;
tail = head;
}else{
tail.setSuccessor(newNode);
newNode.setPredecessor(tail);
tail = newNode;
}
}
우선 우리는 주어진 인터져 t로 새로운 노드 newNode 인스턴스를 생성한다. 그리고 리스트가 empty 상태라면, head 와 tail 인스턴스가 newNode 인스턴스를 참조하게 만든다.
만약 리스트가 empty 상태가 아니라면, tail 인스턴스를 통해 마지막 노드의 successor 필드가newNode를 참조하게 만든다. 그리고 newNode의 predecessor 필드가 tail 인스턴스가 참조하는 노드, 즉 가장 마지막 노드를 참조하게 만든다. 그리고 tail 인스턴스가 새로운 노드인 newNode를 참조하게 만든다.
void removeHead()
 |
| 더블 링크드 리스트 removeHead 메소드 |
이 메소드는 리스트의 가장 첫번째 노드를 삭제한다.
- head 인스턴스가 참조하는 첫번째 노드에 엑세스 한 후, 두번째 노드의 참조값을 얻어온다
- head 인스턴스가 두번째 노드를 참조하게 만든다.
- head 인스턴스를 통해 두번째 노드의 predecessor 필드를 null값으로 변경해, 원래의 첫번째 노드를 참조하는 인스턴스가 없게 만든다
- Java Garbage collector 가 첫번째 노드를 아무도 참조하지 않는것을 알아차렸으니, 이제 첫번째 노드에 할당된 메모리 영역은 다른 리소스들에게 할당될것이다
public void removeHead() {
if (head == tail) {
clear();
} else {
head = head.getSuccessor();
head.setPredecessor(null);
}
}
우선 우리는 head 와 tail 이 같은 값을 참조하는지를 확인한다, 만약 그렇다면 이는 head 와 tail 이 똑같은 null 값을 참조하거나 또는 같은 노드를 참조한다는것을, 즉 리스트에 노드가 1개 밖에 없다는걸 의미한다. 그렇므로 clear() 메소드를 이용해서 리스트의 내용을 모두 지워주면 된다
만약 그렇지 않다면, 우리는 getSuccessor 메소드를 이용해서 head 인스턴스가 두번째 노드를 참조하게 만든다. 그리고 setPredecessor 메소드를 이용하여 head 인스턴스가 참조하는 두번째 노드의 predecessor 필드를 null 값으로 설정한다. 이로써 원래의 첫번째를 참조하는 모든 인스턴스들이 수정됬고, java garbage collector가 곧 원래의 첫번째 노드에 할당된 메모리를 수거할것이다
void removeTail()
 |
| 더블 링크드 리스트 removeTail 메소드 |
이 메소드는 리스트의 가장 마지막 노드를 제거한다
- 마지막 노드를 통해 마지막에서 2번째 노드의 참조값을 얻는다
- tail 인스턴스가 마지막에서 2번째 노드를 참조하게 하여, tail 인스턴스와 마지막 노드의 링크를 파괴한다
- 이제 수정된 tail 인스턴스가 참조하는 마지막에서 2번째 노드의 successor 필드가 null을 참조하게 하여 원래의 마지막 노드를 참조하는 인스턴스가 모두 없어졌다.
public void removeTail(){
if(head==tail){
clear();
}else{
tail = tail.getPredecessor();
tail.setSuccessor(null);
}
}
우선 헤드와 테일 인스턴스가 일치하는지를 확인한다, 일치한다면 이는 리스트에 노드가 1개밖에 없거너 리스트가 empty 상태임을 의미한다. 그러니 그냥 clear 메소드를 이용해서 리스트를 비우자
만약 그렇지 안핟면, getPredecessor() 메소드를 이용, 뒤에서 두번째 노드에 엑세스 한후, tail 인스턴스가 뒤에서 두번째 노드를 가리키도록 만들자. 그리고 나서 바뀐 tail 인스턴스의 successor 필드를 null 로 해준다. 이로써 원래 마지막 노드가 리스트에서 삭제됬다
void remove(int t)
 |
| 더블 링크드 리스트 remove 메소드 |
이 메소드는 인터져 t 를 가진 노드 중 가장 처음에 존재하는 노드를 제거하는 메소드 이다
우선 우리는 가장 첫 노드에서부터 모든 노드를 읽어(traverse) 목적 노드로 엑세스 해야한다.
그 후 아래와 같은 과정들을 거친다.
- 목적 노드의 successor 노드의 참조값을 얻는다
- 얻은 successor 노드의 참조값을 목적노드의 predecessor 노드의 successor 필드가 참조하게 한다.
- 목적 노드의 successor 노드의 predecessor 필드에 접근한다
- 접근한 predecessor 필드가 목적 노드의 predecessor 노드를 참조하게 한다
- 이제 목적노드를 참조하는 모든 인스턴스가 수정되었으니, 곧 java garbage collector 가 목적노드에 할당된 메모리를 수거하게 된다.
public void remove(int t) {
if (!isEmpty()) {
if (head == tail && head.getData() == t) {
clear();
} else {
Node pointer = head;
while (pointer != null) {
if (pointer.getSuccessor().getData() == t) {
pointer.setSuccessor(pointer.getSuccessor().getSuccessor());
pointer.getSuccessor().getSuccessor().setPredecessor(pointer);
break;
}
pointer = pointer.getSuccessor();
}
}
}
}
우선 리스트가 empty상태인지 확인한다, empty 상태라면 제거할 노드가 없으니깐.
empty 상태가 아니라면 head 와 tail 인스턴스가 같은 노드를 참조하는지, 그 노드가 가진 인터져 값이 t 와 일치하는지를 확인한다, 만약 그렇다면 리스트에 1개밖에 없는 노드를 삭제해야되는 것이므로, clear 메소드를 이용해서 리스트를 클리어한다.
만약 아니라면, 와일(While) 루프를 이용해 pointer 인스턴스가 목적 노드의 successor 노드를 참조하게 한다. 그리고 그 successor 노드의 successor 필드가 목적 노드의 successor 노드를 참조하게 한다. 다음으로는, 목적 노드의 successor 노드의 predecessor 필드가 pointer 인스턴스가 참조하는 노드, 즉 목적노드의 predecessor 노드를 참조하게 한다. 그리고 break 구문을 이용해서 루프에서 탈출한다
아래는 자바로 구현된 clear 와 isEmpty 메소드 이다.
private void clear() {
head = tail = null;
}
private boolean isEmpty() {
if (head == null) {
return true;
} else {
return false;
}
}
댓글 없음:
댓글 쓰기