노드 기반 자료 구조

노드란 컴퓨터 메모리 곳곳에 흩어져 있는 데이터 조각이다. 노드 기반 자료 구조는 데이터를 조직하고 접근하는 새로운 방법을 제공하는데 성능상 큰 이점이 많다.

연결 리스트

배열의 경우 연속으로된 빈 셀 그룹에 데이터를 저장 할수 있도록 한다. 하지만 연결 리스트는 다르다. 바로 빈 셀이 연속적인 필요가 없다는 것이다.

[A(1000),1652(1001)],[B(1652),1983(1653)],[C(1983),2001(1984)],[D(2001),null(2002)]
다음과 같은 배열이 있다. 이때 인덱스 0에는 값이 인덱스 1에는 다른 배열로 이어지는 셀 주소를 값으로 가지고 있다. 이 때 인덱스 1을 참조하면 바로 다음 배열로 넘어 갈 수 있는 것이다.
배열을 하나의 노드로 생각하자. 각 노드는 다음 노드로 가는 추가 정보를 가지고 있다.
이 추가 정보(데이터), 다음 노드로의 메모리 주소의 포인터를 우리는 링크라고 부른다.
마지막 노드에는 추가 정보가 들어있지 않다. 이는 연결 리스트의 끝을 의미하기 때문이다.
연결 리스트의 처음을 헤드, 끝을 테일이라고 부른다.
컴퓨터가 연결 리스트의 헤드 주소를 알면, 연결 리스트의 끝까지 방문을 할 수 있다. 각 노드에는 다음 노드로 가는 추가 정보를 가지고 있기 때문에 링크를 따라 리스트를 연결하기만 하면 된다.

데이터가 전체에 흩어질 수 있다는 점에서 연결 리스트는 배열보다 유리 할 수 있다. 연속된 빈 셀 그륩을 찾는 것은 데이터가 많아질 수록 이 작업은 굉장히 어려워진다.

연결 리스트 구현

1. 노드

class node{
    private String data; //노드에 들어 있는 데이터
    private node link; // 다음 노드 주소
    public node(String s){
        this.data = s;
    }
    public void link(node node){
        this.link = node;
    }
    public node nextNode(){
        return link;
    }
    public String getData(){
        return data;
    }

2. 연결 리스트

class linkedList{
    node firstNode;
    linkedList(node node){
        this.firstNode = node;
    }
}

3. main code

    public static void main(String[] args) {
        node node1 = new node("once");
        node node2 = new node("upon");
        node node3 = new node("a");
        node node4 = new node("time");
        node1.link(node2);
        node2.link(node3);
        node3.link(node4);
        linkedList linkedList = new linkedList(node1);
    }

연결 리스트 데이터 읽기

배열의 경우 데이터를 읽는데 O(1)면 충분하다. 하지만 링크드 리스트는 그렇지 않다. 예를 들어 연결 리스트의 마지막 데이터를 읽으려고 한다. 이 때 우리는 연결 리스트의 마지막 주소를 모른다. 이를 알기 위해서 연결 리스트의 헤드를 타고 다음 노드로 넘어가는 작업을 반복 해야한다.
그렇기 때문에 연결 리스트가 데이이터를 읽는데 걸리는 시간 복잡도는 O(N)이다.

코드 구현: 연결 리스트 데이터 읽기

        //리스트의 첫 번째 노드에서 시작한다.
        int currentIndex = 0;
        node currentNode  = firstNode;
        // 찾고 있는 인덱스 보다 같거나 커질 떄까지 다음 노드로 넘어간다.
        while (currentIndex < index){
            currentNode = currentNode.nextNode();
            currentIndex += 1;
        }
        // 현재 노드가 비었다면 null 아니면 노드의 데이터를 반환한다.
        return (currentNode == null) ? null : currentNode.getData();
    }

연결 리스트: 검색

정렬되지 않은 배열의 경우 데이터 검색은 O(N)이다. 연결 리스트 또한 데이터를 선형적으로 검색하므로 시간 복잡도는 O(N)이다.

코드 구현: 연결 리스트 검색

    public Integer search(String s){
        //리스트의 첫 번째 노드에서 시작한다.
        int currentIndex = 0;
        node currentNode  = firstNode;
        //리스트 끝에 도달 할 때까지 다음 노드로 넘어간다.
        while (currentNode != null){
            //다음 같은 같은 찾았다면 인덱스를 리턴한다.
            if (s.equals(currentNode.getData())) return currentIndex;
            currentNode = currentNode.nextNode();
            currentIndex += 1;
        }
        // 값을 찾지 못 했으므로 null을 반환한다.
        return null;
    }

연결 리스트: 삽입

배열의 경우 맨 앞에 데이터를 삽입 하는데 O(N)이 걸린다. 하지만 연결 리스트 경우에는 O(1) 시간 복잡도를 가진다.
맨 앞에 데이터를 삽일 할 경우 삽입 된 노드가 기존 firstNode의 셀 주소를 링크로 가지게 된다. 그후 firtstNode를 삽입된 노드로 변경만 해주면 된다.
[A(1000),1652(1001)],[B(1652),1983(1653)],[C(1983),2001(1984)],[D(2001),null(2002)] 위에 기존 연결리 리스트가 있다. 이 때 [Z(100),null(101)]을 위 리스트에 삽입한다.
이 때 기존 firstNode = [A(1000),1652(1001)]이다
[Z(100),1000(101)]이 되고, 이 후 firstNode = [Z(100),1000(101)]된다.
하지만 연결 리스트는 맨 뒤에 데이터를 삽입 할 경우 O(N)이 걸린다. 리스트의 맨 마지막 셀을 찾으려면 N번의 단계가 필요 하기 때문이다.
그렇다면 배열과 연결 리스트의 삽입 차이는 어떨까??

코드 구현: 연결 리스트 삽입

    public void insert(int index, String s){
        // 전달 받은 데이터로 새로운 노드를 생성
        node newNode = new node(s);
        // 맨 앞에 삽입 할 경우
        if (index == 0) {
            //새로운 노드 다음 노드에 첫 노드를 가리키게 한다.
            newNode.link(this.firstNode);
            //헤드를 새로운 노드로 변경한다.
            firstNode = newNode;
        }
        //맨 앞이 아닌 경우
        node currentNode = firstNode;
        int currentIndex = 0;
        // 연결 리스트 끝까지 확인
        while (currentIndex < index - 1){
            currentNode = currentNode.nextNode();
            currentIndex += 1;
        }
        //새로운 노드가 현 노드의 다음 노드를 가리키게 한다.
        newNode.link(currentNode);
        //현 노드가 새로운 노드를 가리키게 한다.
        currentNode.link(newNode);
    }

연결 리스트: 삭제

연결 리스트는 삭제를 앞에서 하는 경우 O(1)이다. 헤드가 두 번째 노드를 가리키게 하면 끝이기 때문이다.
하지만 최악의 경우는 O(N)이다. 마지막 노드를 삭제하기 위해서는 연결 리스트를 타고 마지막으로 노드까지 가야 한다.
최선 O(1) 최악 O(N)

상황	배열	연결 리스트
앞에서 삭제	최악의 경우	최선의 경우
중간에서 삭제	평균적인 경우	최악의 경우
끝에서 삭제	최선의 경우	최악의 경우

연결 리스트에서 노드를 삭제해도 여전히 메모리 어디가에 삭제된 노드가 존재한다. 하지만 리스트에 연결 고리를 제거하므로 연결 리스트에서는 제거된다.
어떠한 프로그래밍 언어는 자동으로 쓰이지 않는 노드를 자동으로 감지해 메모리를 해제(가비지 컬렉트)한다.

코드 구현: 연결 리스트 삭제

    public void delete(int index){
        // 삭제하려는 노드가 헤드라면 두 번째 노드를 헤드로 만든다.
        if (index == 0) firstNode = firstNode.nextNode();
        //헤드가 아니라면
        node currentNode = firstNode;
        int currentIndex = 0;
        //삭제하려는 노드 앞 노드를 찾는다.
        while (currentIndex < index - 1){
            currentNode = currentNode.nextNode();
            currentIndex += 1;
        }
        //삭제하려는 노드 다음 노드를 이전 노드에 링크로 변경한다.
        currentNode.link(currentNode.nextNode().nextNode());
    }

연결 리스트 연산의 효율성

연결 리스트와 배열 비교

연산	배열	연결 리스트
읽기	O(1)	O(N)
검색	O(N)	O(N)
삽입	O(N) 끝에서 하면O(1)	O(N) 앞에서 하면O(1)
삭제	O(N) 끝에서 하면O(1)	O(N) 앞에서 하면O(1)

이렇게 표를 보면, 배열에 비슷한 기능을 하는 연결 리스트지만, 읽기는 훨씬 느라다.
하지만 이러한 연결 리스트 배열 보다 효율적으로 사용하는 시나리오가 있다.

연결 리스트 다루기

연결 리스트가 효율적인 시나리오는 한 리스트를 검사해서 많은 원소를 삭제할 때다.
예를 들어 사용자가 만명인 데이터 베이스가 있다. 이 때 사용자가 탈퇴하여 사용자 계정을 지우려고 한다. 이 경우 배열과 연결 리스트는 몇 단계가 걸리게 될까??
배열과 연결 리스트 모두 사용자를 검색 하는데 O(N)이 걸린다. 하지만 삭제 때는 다르다.
바로 쉬프트의 차이다. 배열의 경우 데이터를 삭제하면 쉬프트 연산을 수행해야한다.
하지만 연결 리스트는 쉬프트 연산을 수행하지 않는다.
그렇기에 연결 리스트 전체 리스트를 확인하면서 삽입이나 삭제를 수행하기 알맞은 자료구조다.

이중 연결 리스트

연결 리스트는 다양 종류가 있다. 이 중 하나가 연결 리스트를 변형시킨 이중 연결 리스트다.
이중 연결리스트는 각 노드에 2개의 링크가 있다. 이 때 한 링크는 앞 노드를, 다른 한 링크는 뒷 노드를 가리킨다.
[null,"A(1001)",2001] [1001,"B(2001)",3001] [2001,"C(3001)",null]

코드 구현: 이중 연결 리스트

node

class node2{
    private String data; //노드에 들어 있는 데이터
    private node2 previousLink; // 다음 노드 주소
    private node2 nextLink;// 이전 노드 주소
    public node2(String s){this.data = s;}//새로운 노드 생성시
    public void setPreviousLink(node2 node2){this.previousLink = node2;} // 이전 노드 링크
    public void setNextLink(node2 node2){this.nextLink = node2;} // 다음 노드 링크
    public node2 nextNode(){return previousLink;} // 다음 노드 반환
    public node2 previousNode() {return nextLink;}// 이전 노드 반환
    public String getData(){return data;} // 노드의 데이터 반환
}

DoublyLinkedList

class doublyLinkedList{
    private node2 nextNode;
    private node2 previousNode;
    public doublyLinkedList(node2 previousNode, node2 nextNode){
        this.nextNode = nextNode;
        this.previousNode = previousNode;
    }
}

코드 구현: 이중 연결 리스트 삽입

    public void insert(String data){
        //리스트가 비어있다면
        node2 newNode = new node2(data);
        if (this.firstNode == null){
            this.firstNode = newNode; // 헤드를 새로운 노드 주소로 설정.
            this.lastNode = newNode; // 태일을 새로운 노드 주소로 설정.
        }
        //리스트가 비어 있지 않다면,
        else {
            newNode.setPreviousLink(this.lastNode); // 새로운 노드의 이전 노드를 마지막 노드로 설정.
            this.lastNode.setNextLink(newNode); // 마지막 노드의 다음 주소를 새로운 노드로 설정.
            this.lastNode = newNode; // 마지막 노드는 새로운 노드로 설정.
        }
    }

앞과 뒤로 이동

기존 연결 리스트 전형적인 연결 리스트는 다음 링크로만 이동이 가능하고, 이전 노드로는 이동 할 수 없었다.
하지만 이중 연결 리스트는 이와 달리 앞과 뒤로 모두 이동을 할수 있어 훨씬 유연하다. 마지막 노드에서 시작해서 첫 노드로 갈수 있다.

이중 연결 리스트 기반 큐

이중 연결 리스트는 삽입과 삭제 모두 끝과 시작에서 O(1) 시간 복잡도를 가진다.
이러한 특성은 큐를 위한 완벽한 내부 자료구조이다.
이전의 큐는 데이터를 끝에만 삽입하고, 앞에서만 삭제할 수 있었다. 이전 큐가 추상 데아터 타입의 하나이며 배열을 사용하여 내부적으로 큐를 구현 할 수 있다고 배웠다.
큐는 끝에서 삽입, 앞에서 삭제 하므로 내부 자료 구조로 배열이 효율적이다. 배열은 끝에 삽입이 O(1) 앞에서 삭제가 O(N)이다.
반면 이중 연결 리스트는 끝에서 삽입, 앞에서 삭제 모두 O(1)이다. 따라서 큐의 내부 자료 구조로 완벽하다.

코드 구현: 이중 연결 리스트 기반 큐

class node2{
    private String data; //노드에 들어 있는 데이터
    private node2 previousLink; // 다음 노드 주소
    private node2 nextLink;// 이전 노드 주소
    public node2(String s){this.data = s;}//새로운 노드 생성시
    public void setPreviousLink(node2 node2){this.previousLink = node2;} // 이전 노드 링크
    public void setNextLink(node2 node2){this.nextLink = node2;} // 다음 노드 링크
    public node2 nextNode(){return previousLink;} // 다음 노드 반환
    public node2 previousNode() {return nextLink;}// 이전 노드 반환
    public String getData(){return data;} // 노드의 데이터 반환
}

class doublyLinkedList{
    private node2 firstNode;
    private node2 lastNode;
    public doublyLinkedList(node2 firstNode, node2 lastNode){
        this.firstNode = firstNode;
        this.lastNode = lastNode;
    }
    public doublyLinkedList(){}
    public void insert(String data){
        //리스트가 비어있다면
        node2 newNode = new node2(data);
        if (this.firstNode == null){
            this.firstNode = newNode; // 헤드를 새로운 노드 주소로 설정.
            this.lastNode = newNode; // 태일을 새로운 노드 주소로 설정.
        }
        //리스트가 비어 있지 않다면,
        else {
            newNode.setPreviousLink(this.lastNode); // 새로운 노드의 이전 노드를 마지막 노드로 설정.
            this.lastNode.setNextLink(newNode); // 마지막 노드의 다음 주소를 새로운 노드로 설정.
            this.lastNode = newNode; // 마지막 노드는 새로운 노드로 설정.
        }
    }
    public node2 removeFront(){
        node2 removedNode = this.firstNode;
        this.firstNode = firstNode.nextNode();
        return removedNode;
    }
    public node2 getFirstNode(){return firstNode;}
    public node2 getLastNode() {
        return lastNode;
    }
}

class Queue{
    private doublyLinkedList doublyLinkedList;
    public Queue(){ this.doublyLinkedList = new doublyLinkedList();} //큐 생성시 새로운 이중 연결 리스트를 설정.
    public void enqueue(String data){ //큐에 데이터를 넣을 때
        doublyLinkedList.insert(data); 
    }
    public String dequeue(){// 큐 데이터를 삭제할 때
        node2 removedNode = doublyLinkedList.removeFront();
        return removedNode.getData();
    }
    public String read(){ // 큐에서 데이터를 삭제하지 않고 읽기.
        if (doublyLinkedList == null) return null;
        return doublyLinkedList.getFirstNode().getData();
    }
}

이중 연결리스트로 큐를 구현 함으로써 삽제와 삽입 모두 O(1)로 할 수 있는 큐를 구현했다.

결론

연결 리스트는 대규모 데이터에서 삭제와 삽입을 할 때 아주 효휼성이 뛰어난 자료구조이다.
또한 큐에 추상적인 자료 구조로 사용하기에 매우 어울린다. 그렇기에 연결 리스트의 개념에 대하여 제대로 이해 할 필요가 있다.