자료구조 :: JAVA를 이용한 이중 연결 리스트 (Doubly Linked List) 구현하기

이중 연결 리스트 (Doubly Linked List)

doubly linked list의 핵심은 노드와 노드가 서로 연결되어 있다는 점이다.

(단일 연결 리스트는 한쪽 방향으로 연결되어 있지만, 이중연결리스트는 쌍방향으로 연결되어있다.)

 

 

여기서는 이전노드를 prevNode라 명한다.

 

 

장점

'이중 연결 리스트'의 큰 장점은 양방향으로 연결되어 있기 때문에,

노드를 탐색하는 방향이 양쪽으로 가능하다는 것이다.

 

단일연결리스트의 경우는 맨끝의 데이터를 가져올때,

순차적으로 처음노드(head)부터 탐색을 해야한다.

(많은 연산을 필요로 한다.)

 

이러한 단점을 보완할 수 있는 것이 '이중연결리스트'이다.

이중연결리스트는 처음 부터 탐색 할 필요 없이 뒤(tail)에서 부터 탐색을 시작하면 된다.

 

 

단점

이전 노드를 지정하기 위한 변수를 하나 더 사용해야 한다. (메모리를 더 많이 사용함)

구현이 '단일연결리스트'에 비해 복잡하다.

 

하지만, 장점이 크기 때문에 현실에서는 대부분 이중 연결 리스트를 많이 사용한다.

 

 

구현 단계

노드 클래스를 만든다.

public class MyDoublyLinkedList {
 
    private Node head;
    private Node tail;
    private int size;
 
    public MyDoublyLinkedList() {
        size = 0;
    }
 
    private class Node {
        // 단일 연결 리스트와의 차이점은
        // 이전 노드를 기록할 수 있는 변수를 가지고 있다.
        private Node nextNode;
        private Node prevNode; // *
        private Object data;
 
        Node(Object data) {
            this.data = data;
            this.nextNode = null;
            this.prevNode = null;
        }
    }
}
​

 

 

데이터 추가

새로운 노드를 생성한다.

 

 

기존 노드간의 연결을 끊고,

새로운 노드와의 연결을 구성한다.

 

 

public void addFirst(Object data) {
    Node newNode = new Node(data);
 
    if (head != null) {
        // 기존 노드가 있음
        newNode.nextNode = head;
        head.prevNode = newNode;
    }
 
    head = newNode;
    if (head.nextNode == null) {
        tail = head;
    }
    size++;
}​

addFirst() 메소드는 리스트의 맨 처음 부분에 데이터를 넣어주는 기능을 한다.

 

public void addLast(Object data) {
    if (size == 0) {
        addFirst(data);
    } else {
        Node newNode = new Node(data);
        tail.nextNode = newNode;
        newNode.prevNode = tail;
        tail = newNode;
        size++;
    }
}​

addLast() 메소드는 리스트의 맨 끝 부분에 데이터를 넣어주는 기능을 한다.

(addFirst()와 반대 기능)

 

public void add(int index, Object data) {
    if (index == 0) {
        addFirst(data);
    } else if (index == size - 1) {
        addLast(data);
    } else {
        Node newNode = new Node(data);
        Node prevNode = getNode(index - 1);
        Node nextNode = prevNode.nextNode;
        // 추가된 노드의 전후 설정
        newNode.prevNode = prevNode;
        newNode.nextNode = nextNode;
 
        // 이전 노드의 전후 설정
        prevNode.nextNode = newNode;
 
        // 다음 노드의 전후 설정
        nextNode.prevNode = newNode;
 
        size++;
    }
}​

add() 메소드는 Index를 이용하여, 원하는 위치에 데이터를 넣어주는 기능을 한다.

 

index가 0일때와 index가 size-1 일때는, 미리 만들어 둔 addFirst(), addLast() 메소드를 이용한다.

(반복된 연산을 피할 수 있음)

 

private Node getNode(int index) {
    if (index < size / 2) {
        Node node = head;
        for (int i = 0; i < index; i++) {
            node = node.nextNode;
        }
        return node;
    } else {
        Node node = tail;
        for (int i = size - 1; i > index; i--) {
            node = node.prevNode;
        }
        return node;
    }
}
​

getNode()는 index를 이용하여 해당 위치의 Node를 가져오는 메소드이다.

 

데이터 지우기

제거할 노드를 탐색한다.

 

제거할 노드의 양 옆 링크 연결을 해제하고,

제거한 노드 양 옆의 노드간의 링크를 설정한다. (prevNode와 nextNode)

 

// 지우기
public Object removeFirst() {
    if(size == 0) {
        return null;
    }
    
    Node removeNode = head;
    head = null;
    head = removeNode.nextNode;
    head.prevNode = null;
    size--;
    
    return removeNode.data;
}​

removeFirst() 메소드는 맨 앞 부분의 노드를 지우고 데이터를 반환한다.

 

public Object removeLast() {
    if(size == 0) {
        return null;
    }
    
    Node removeNode = tail;
    tail = null;
    tail = removeNode.prevNode;
    tail.nextNode = null;
    size--;
    
    return removeNode.data;
}​

removeLast() 메소드는 맨 끝 부분의 노드를 지우고 데이터를 반환한다.

 

public Object remove(int index) {
    if(size == 0) {
        return null;
    }
    
    if(index == 0) {
        return removeFirst();
    }else if(index == size-1) {
        return removeLast();
    }else {
        Node removeNode = getNode(index);
        Node prevNode = removeNode.prevNode;
        Node nextNode = removeNode.nextNode;
        
        // 이전 노드 전후 설정
        prevNode.nextNode = nextNode;
        
        // 다음 노드 전후 설정
        nextNode.prevNode = prevNode;
        
        size--;
        
        return removeNode.data;
    }
}
​

remove() 메소드는 index 를 이용하여 해당 위치의 노드를 지우고, 데이터를 반환한다.

 

 

전체 코드

public class MyDoublyLinkedList {
 
    private Node head;
    private Node tail;
    private int size;
 
    public MyDoublyLinkedList() {
        size = 0;
    }
 
    public void addFirst(Object data) {
        Node newNode = new Node(data);
    
        if (head != null) {
            // 기존 노드가 있음
            newNode.nextNode = head;
            head.prevNode = newNode;
        }
    
        head = newNode;
        if (head.nextNode == null) {
            tail = head;
        }
        size++;
    }
 
    public void addLast(Object data) {
        if (size == 0) {
            addFirst(data);
        } else {
            Node newNode = new Node(data);
            tail.nextNode = newNode;
            newNode.prevNode = tail;
            tail = newNode;
            size++;
        }
    }
 
    public void add(int index, Object data) {
        if (index == 0) {
            addFirst(data);
        } else if (index == size - 1) {
            addLast(data);
        } else {
            Node newNode = new Node(data);
            Node prevNode = getNode(index - 1);
            Node nextNode = prevNode.nextNode;
            // 추가된 노드의 전후 설정
            newNode.prevNode = prevNode;
            newNode.nextNode = nextNode;
    
            // 이전 노드의 전후 설정
            prevNode.nextNode = newNode;
    
            // 다음 노드의 전후 설정
            nextNode.prevNode = newNode;
    
            size++;
        }
    }
 
    // 지우기
    public Object removeFirst() {
        if(size == 0) {
            return null;
        }
        
        Node removeNode = head;
        head = null;
        head = removeNode.nextNode;
        head.prevNode = null;
        size--;
        
        return removeNode.data;
    }
    
    public Object removeLast() {
        if(size == 0) {
            return null;
        }
        
        Node removeNode = tail;
        tail = null;
        tail = removeNode.prevNode;
        tail.nextNode = null;
        size--;
        
        return removeNode.data;
    }
    
    public Object remove(int index) {
        if(size == 0) {
            return null;
        }
        
        if(index == 0) {
            return removeFirst();
        }else if(index == size-1) {
            return removeLast();
        }else {
            Node removeNode = getNode(index);
            Node prevNode = removeNode.prevNode;
            Node nextNode = removeNode.nextNode;
            
            // 이전 노드 전후 설정
            prevNode.nextNode = nextNode;
            
            // 다음 노드 전후 설정
            nextNode.prevNode = prevNode;
            
            size--;
            
            return removeNode.data;
        }
    }
    
    private Node getNode(int index) {
        if (index < size / 2) {
            Node node = head;
            for (int i = 0; i < index; i++) {
                node = node.nextNode;
            }
            return node;
        } else {
            Node node = tail;
            for (int i = size - 1; i > index; i--) {
                node = node.prevNode;
            }
            return node;
        }
    }
 
    public String toString() {
        StringBuffer result = new StringBuffer("[");
        if (size != 0) {
            Node node = head;
            result.append(node.data);
            while (node.nextNode != null) {
                node = node.nextNode;
                result.append(", ");
                result.append(node.data);
            }
        }
        result.append("]");
        return result.toString();
    }
 
    private class Node {
        // 단일 연결 리스트와의 차이점은
        // 이전 노드를 기록할 수 있는 변수를 가지고 있다.
        private Node nextNode;
        private Node prevNode; // *
        private Object data;
 
        Node(Object data) {
            this.data = data;
            this.nextNode = null;
            this.prevNode = null;
        }
    }
 
    public static void main(String[] args) {
        MyDoublyLinkedList list = new MyDoublyLinkedList();
        list.addFirst(40);
        list.addFirst(30);
        list.addFirst(20);
        list.addFirst(10);
        System.out.println(list.toString()); // 10 20 30 40
 
        list.add(2, 25); // 10 20 25 30 40
        System.out.println(list.toString());
 
        list.addLast(50);
        System.out.println(list.toString()); // 10 20 25 30 40 50
        
        list.removeFirst();
        System.out.println(list.toString()); // 20 25 30 40 50
 
        list.removeLast();
        System.out.println(list.toString()); // 20 25 30 40
        
        list.remove(1);
        System.out.println(list.toString()); // 20 30 40
        
    }
}​

 

관련 글

2018/04/19 - [ETC] - 자료구조 :: JAVA를 이용한 단일 연결 리스트 LinkedList 구현하기