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

정의 #

각 리스트의 노드가 이전노드, 다음노드를 가리키는 포인터가 존재한다. 따라서 노드의 이동이 자유로운 장점이 있다. 하지만 노드의 추가/삭제 시 관리 해야할 요소가 많아지는 단점이 있다.

배열과 차이점 #

이중연결리스트 데이터 삽입 구조

배열(Array)은 구조가 단순하기 때문에 관리가 용이하다. 하지만 배열의 중간의 Index가 삭제되어 데이터가 없게 된다 그 배열 Index는 특별한 처리를 하지 않는한 null이 된다. 따라서 배열은 쓸데없는 메모리 공간을 차지할 수 있다. 하지만 이중 연결리스트는 중간의 데이터가 삭제되면 데이터만 사라지고 삭제된 노드의 이전 노드가 삭제된 다음 노드를 가리키는 것으로 수정되기 때문에 메모리 공간을 낭비할 필요가 없어진다.

간단한 구현(java) #

public class DoublyLinkedList {

private Node header;
private int size;
public DoublyLinkedList(){
    header = new Node(null);
    size=0;
    }

//node의 초기상태
//처음 노드는 이전 노드(previousNode)가 null이되며
//마지막 노드는 다음 노드(nextNode)가 null이 된다.
private  class Node{

    private Object data;
    private Node previousNode;
    private Node nextNode;

    Node(Object data){

        this.data = data;
        this.previousNode = null;
        this.nextNode = null;

        }
    }
}

//데이터 탐색
/*
이중 연결 리스트는 지정한 위치의 노드를 꺼내기 위해서 index 값이 데이터의 앞부분에 있을 경우(index < size/2) 처음 노드부터 순방향으로 탐색을 하고 index 값이 데이터의 뒷부분에 있을 경우 (index >= size/2) 마지막 노드부터 역방향으로 탐색을 시도한다.

평균적으로 순방향의 경우나 역방향의 경우 모두 데이터수/4 만큼의 순차접근을 처리하므로 전체적인 효율은 단순 연결 리스트의 2배가 된다.
*/
public Object get(int index){
    return getNode(index).data;
}

private Node getNode(int index){

    if(index < 0 || index > size){
        throw new IndexOutOfBoundsException("Index : "+index+", Size : " + size);
    }

    Node node = header;

    // index 가 리스트 size의 중간 앞이면 순차적으로 탐색한다.
    if(index < (size/2)){

        for(int i =0; i<=index; i++){
            node = node.nextNode;
        }

    }else{
        // index가 리스트 size의 중간보다 뒤면 뒤에서부터 탐색한다.
        for(int i = size; i > index; i--){
            node = node.previousNode;

        }
    }

    return node;
}

//데이터 삽입
public void addFirst(Object data){

    // 데이터를 담은 새로운 노드 생성
    Node newNode = new Node(data);

    // 새로운 노드가 다음 노드로 첫번째 노드를 가리킨다.
    newNode.nextNode = header.nextNode;

    // 리스트가 비어있지 않으면
    if(header.nextNode != null){

        // 첫 노드가 자신의 앞 노드로 새로운 노드를 가리킨다.
        header.nextNode.previousNode = newNode;

    }else{    // 리스트가 비어있으면

        // 헤더가 마지막 노드를 새로운 노드로 가리키도록 한다.
        header.previousNode = newNode;

    }

    // 헤더가 첫번째 노드로 새로운 노드를 가리키도록 한다.
    header.nextNode = newNode;
    size++;
}

//데이터 삭제
public Object removeFirst(){

    // 첫번째 노드를 가져온다.
    Node firstNode = getNode(0);

    // 헤더가 첫 노드로 두번째 노드를 가리킨다.
    header.nextNode = firstNode.nextNode;

    // 리스트가 비어있지 않을 때
    if(header.nextNode != null){

        // 두번째 노드가 가리키는 앞 노드는 없다.
        firstNode.nextNode.previousNode = null;

    }else{ // 리스트가 비게 되면

        // 헤더가 가리키는 마지막 노드가 없다.
        header.previousNode = null;

    }

    size--;
   // 첫번째 노드의 데이터를 반환
    return firstNode.data;
}