Doubly Linked List(이중 연결 리스트) (Java)
Doubly Linked List는 Singly Linked List(단일 연결 리스트)의 확장된 개념이다. 단일 연결 리스트는 맨 처음 노드에서 맨 끝 노드로 순차적으로 이동하면서 원하는 정보를 담은 노드를 탐색할 수 있다. 하지만 반대로 맨 뒤에서 앞으로는 탐색이 불가능하다. 왜냐하면 노드가 자신의 앞 노드의 정보를 가지고 있지 않기 때문이다.
반면, 이중 연결 리스트는 뒤에서 앞으로도 탐색이 가능하다. 단일 연결 리스트의 각 노드에 앞 노드의 정보를 추가해주는 작업을 더해주면 이중 연결 리스트를 구현한 것이다.
장점
이중 연결 리스트의 장점은 탐색에서 드러난다. 원하는 노드가 어느 위치(index)에 있는지도 알고 있다면, 노드의 위치를 리스트의 길이의 반과 비교해서 더 빠르게 탐색할 수 있는 지점(head or tail)을 선별하는게 가능하기 때문이다. 이러면 단일 연결 리스트보다 더 빠르게 탐색할 수 있다.
단점
그러나 노드가 가지는 정보의 수가 더 늘어나는 것은 메모리 사용 증가로 이어진다.
오늘은 삽입, 삭제, 탐색을 이중 연결 리스트에 구현할 생각이다.
데이터는 모두 오름차순으로 정렬되게 삽입 메서드를 구현했다.
package LinkedList;
public class DoublyLinkedList {
class Node{
int data;
Node previous, next;
Node(int data){
this.data = data;
}
}
Node head, tail;
int size;
DoublyLinkedList() {
// 생성자는 딱히 필요없음.
}
public void insert(int data) {
}
public Node delete(int index) {
}
public Node getHead() {return head;}
public Node getTail() {return tail;}
public Node getNode(int index) {
}
public void printForward() {
}
public void printBackward() {
}
}기본 틀을 짜보았다. 이젠 이 메서드들이 제 기능을 하도록 안에 구현할 것이다.
insert method (삽입 메서드)
insert 메서드는 오름차순으로 정렬되도록 노드를 삽입할 예정이다. 삽입을 하더라도 여러 case를 떠올릴 수 있다.
case 0 : list에 아무것도 없는 경우
case 1 : new data가 가장 큰 경우
case 2 : new data가 중간에 삽입되는 경우
case 3 : new data가 가장 작은 경우
하나하나 살피면서 문제 상황을 이해하고 구현해보기로 했다.
case 0 : list에 아무것도 없는 경우
이 경우는 이중 연결 리스트를 생성하고난 다음, 데이터를 처음 입력하는 경우이다. 그래서 head와 tail을 새 노드로 설정해주었다.
tail을 new Node(data)로 한 이유는 java 공부를 한 지 너무 오래 돼서 head와 tail이 같은 메모리 주소를 가리켜서 나중에 문제가 생길까봐 이렇게 했다..
public void insert(int data) {
Node node = new Node(data);
if (size == 0){
head = node;
tail = new Node(data);
size++;
return;
}
case 1 : new data가 가장 큰 경우
이게 무슨 말이냐면, 새 데이터가 연결 리스트의 가장 뒤에 가야 하는 경우이다. 그래서 이 경우에는 tail을 새로 설정해주어야 한다.
current node의 data보다 new data가 더 큰 값이면, current node의 next와 비교해야 한다. 그런데 이때 주의해야 할 점이 있다. current node의 next가 null, 즉 current node가 이중 연결 리스트의 tail인 경우를 주의해야 한다.
만약 현재 노드(current node)가 tail이라면 (1)tail을 new node로 새롭게 설정해준다. (2)그 다음 현재 노드의 next와 new node의 previous를 알맞게 설정해준다.
if (current.data < node.data) {
// 현재 노드가 tail인 경우 (현재 노드가 가장 큰 경우)
if (current.next == null) {
tail = node;
node.previous = current;
current.next = node;
return;
}
// 그게 아니면 다음 노드를 탐색한다.
current = current.next;
}case 2 : new data가 중간에 삽입되는 경우
이번 case는 머리로만 구현하기에는 어려워서 결국 태블릿에 그리면서 했다. 덕분에 금방 구현할 수 있었다.
위 로직대로 따라가기만 하면 중간에 삽입하는 일은 쉽다. 심지어 case3(new node가 가장 작은 경우)도 한 번에 처리가 가능했다.
else if(current.data >= node.data) {
node.next = current; //(1)
node.previous = current.previous; //(2) // current == head일 땐 어차피 head.previous == null이라 상관없는 코드.
if (current.previous == null) { // current가 head인 경우
current.previous = node; //기존 head의 previous 설정
head = node;
return;
}
current.previous.next = node; //(3)
current.previous = node; //(4)
return;
}getNode method (탐색 메서드)
단순하게 while 반복문을 통해서 입력한 index의 node를 탐색하고 return해준다.
만약 index가 리스트의 최대 인덱스보다 크다면, tail을 반환하도록 했다.
public Node getNode(int index) {
if (index < 0 || size-1 < index){
return null;
}
Node node = null;
if (index < size/2) {
node = searchForward(index);
} else {
node = searchBackward(index);
}
return node;
}
private Node searchForward(int index) {
Node current = head;
int idx = 0;
while (idx++ < index){
current = current.next;
}
return current;
}
private Node searchBackward(int index) {
Node current = tail;
int idx = size-1;
while (idx-- > index) {
current = current.previous;
}
return current;
}delete method (삭제 메서드)
입력한 index에 해당하는 노드를 삭제한다. 혹시 실수할까봐 삭제되는 과정을 그려보았다.
- 지우고자 하는 노드(target)의 previous.next를 target.next로 바꾼다.
- 또, 지우고자 하는 노드(target)의 next.previous를 target.previous로 바꾼다.
그러나 target이 head 또는 tail인 경우도 존재한다. 이런 경우는 if 문으로 대처가 가능하다.
public Node delete(int index) {
if (index < 0 || size-1 < index) {
System.out.println("Invalid index entered.");
return null;
}
Node target = getNode(index); // target이 head 또는 tail인 경우가 존재
// head인 경우
if (target.previous == null) {
head = target.next;
target.next.previous = null;
}
// tail인 경우
else if (target.next == null) {
tail = target.previous;
target.previous.next = null;
}
// 나머지의 경우
else {
target.previous.next = target.next; //(1)
target.next.previous = target.previous; //(2)
System.out.println("delete completion");
}
return target;
}
전체 코드
package LinkedList;
public class DoublyLinkedList {
class Node{
int data;
Node previous, next;
Node(int data){
this.data = data;
}
}
Node head, tail;
int size;
DoublyLinkedList() {
// 생성자는 딱히 필요없음.
}
public void insert(int data) {
Node node = new Node(data);
if (size == 0){
head = node;
tail = new Node(data);
size++;
return;
}
size++;
Node current = head;
while(current != null) {
if (current.data < node.data) {
// 현재 노드가 tail인 경우 (현재 노드가 가장 큰 경우)
if (current.next == null) {
tail = node;
node.previous = current;
current.next = node;
return;
}
// 그게 아니면 다음 노드를 탐색한다.
current = current.next;
}
else if(current.data >= node.data) {
node.next = current;
node.previous = current.previous; // current == head일 땐 어차피 head.previous == null이라 상관없는 코드.
if (current.previous == null) {
current.previous = node;
head = node;
return;
}
current.previous.next = node;
current.previous = node;
return;
}
}
}
public Node delete(int index) {
if (index < 0 || size-1 < index) {
System.out.println("Invalid index entered.");
return null;
}
Node target = getNode(index); // target이 head 또는 tail인 경우가 존재
// head인 경우
if (target.previous == null) {
head = target.next;
target.next.previous = null;
}
// tail인 경우
else if (target.next == null) {
tail = target.previous;
target.previous.next = null;
}
// 나머지의 경우
else {
target.previous.next = target.next;
target.next.previous = target.previous;
System.out.println("delete completion");
}
return target;
}
public Node getHead() {return head;}
public Node getTail() {return tail;}
public Node getNode(int index) {
if (index < 0 || size-1 < index){
return null;
}
Node node = null;
if (index < size/2) {
node = searchForward(index);
} else {
node = searchBackward(index);
}
return node;
}
private Node searchForward(int index) {
Node current = head;
int idx = 0;
while (idx++ < index){
current = current.next;
}
return current;
}
private Node searchBackward(int index) {
Node current = tail;
int idx = size-1;
while (idx-- > index) {
current = current.previous;
}
return current;
}
public void printForward() {
Node node = head;
int count = 1;
System.out.println("[print Forward 실행]");
while (node != null) {
System.out.printf("%d번째 노드 | data : %d\n", count++, node.data);
node = node.next;
}
// System.out.println("= = = = = = = = = = = = = = = = = = = = = = =");
}
public void printBackward() {
Node node = tail;
int count = 1;
System.out.println("[print Backward 실행]");
while (node != null) {
System.out.printf("%d번째 노드 | data : %d\n", count++, node.data);
node = node.previous;
}
}
}print 메서드는 현재 노드의 previous 또는 next로 계속 이동하면서 노드를 출력하는 것이다.
tail부터 출력하면 내림차순으로 출력한다.