연결리스트

일차원 배열을 사용한 곳에는 대부분 배열을 연결리스트로 바꿀 수 있다.(단 연결리스트는 리스트요소의 임의 접근을 지원하지 않는다.) 임의의 요소에 접근해야 할 때는 연결리스트보다 배열이 좋다.

연결리스트 정의

노드(Node)라 불리는 객체가 모여 연결 리스트를 구성한다. 각 노드는 객체 레퍼런스를 통해 리스트의 다른 노드와 연결된다. 다른 노드를 참조하는 레퍼런스를 링크(link)라고 한다.

Milk -> Bread -> Eggs --> Bacon -- null

인덱스로 요소를 참조할 수 있는 배열과 달리 연결리스트의 요소는 다른요소와의 관계를 통해 원하는 요소를 참조할 수있다. 예를들어 Bread가 두번째 위치에 있다고 표현하는것이 아니라, Milk 다음에 있다고 표현한다.

연결리스트에서는 첫번째 노드에서 마지막 노드로 이동하는 방식으로 전체요소를 확인할 수 있다.(종종 연결리스트에서는 헤더 노드를 시작점으로 사용하는데 여기서는 헤더 노드는 방문대상에서 제외시킨다.)

Header -> Milk -> Bread -> Eggs --> Bacon -- null

연결리스트에 간단하게 새 노드를 추가할 수 있다. 새 노드를 추가하려면 삽입하려는 노드의 이전노드(previous node) 링크가 새노드를 가리키도록 바꿔야 하고 새노드의 링크는 이전노드가 가리키던 노드를 가리키도록 설정해야 한다.

Header -> Milk -> Bread -> Eggs       Bacon -- null
                            └─ Cookies ─┘

연결리스트의 항목을 삭제하는 일도 간단한 편이다. 삭제하려는 노드의 이전에 있는 노드 링크를 삭제하려는 노드가 가리키는 노드로 바꾼다음, 삭제하려는 노드의 링크를 null로 설정하면 노드가 삭제된다.

연결 리스트는 다른 다양한 함수도 제공하는데, 이중에서 특히 삽입(insert)과 삭제 동작(remove)은 왜 연결리스트가 유용한지를 가장 명확히 보여준다.

객체 기반 연결 리스트 설계

연결 리스트에서는 두 클래스를 만들어야 한다. 우선 연결 리스트에 추가할 수 있는 Node 클래스와 LinkedList 클래스를 만든다. LinkedList클래스는 노드의 삽입(insert), 삭제(remove), 리스트출력(display), 기타 연결 리스트에 필요한 기능을 제공한다.

Node클래스

Node클래스는 노드의 데이터를 저장하는element와 연결리스트이 다음노드링크를 저장하는 next 두가지 프로퍼티를 포함한다.

function Node(element){
    this.element = element;
    this.next = null;
}

LinkedList(LList) 클래스

LList클래스는 연결 리스트의 기능을 제공한다. LList클래스는 새노드 삽입(insert), 삭제(remove), 리스트의 특정데이터 검색(find)등의 기능을 제공한다.

function LList(){
    this.head = new Node("head");
}

LList.prototype.find = function(item){...}
LList.prototype.insert = function(){...};
LList.prototype.remove = function(){...};
LList.prototype.display = function(){...};

새로운 노드 삽입하기

먼저 리스트에 노드를 추가하는 insert함수를 살펴보자. 노드를 추가하려면 어떤 노드를 추가할 것이고, 어느 노드의 뒤 혹은 앞에 추가할지를 지정해야 한다. 예제에서는 기존노드 뒤로 노드를 추가한다고 가정한다.

기존노드의 뒤에 새노드를 추가하려면 기존 노드를 찾아야하기 때문에 리스트에서 특정 데이터를 포함하는 노드를 검색하는 **find()*8함수를 구현한다.

LList.prototype.find = function(item){
    var currNode = this.head;
    //currNode.element가 item과 같은 값일때까지 될때
    //currNode.next를 계속 돌려서 저장한다.
    while(currNode.element != item){
        currNode = currNode.next;
    }
    return currNode;
}

find()함수는 연결 리스트를 탐색하는 방법을 보여준다. 우선 새 노드를 만들고 head 노드로 설정한다. 그리고 다음 노드로 반복 이동하면서 현재노드의 element프로퍼티가 탐색하려는 값과 같은 값을 포함하는지 확인한다. 원하는 데이터를 찾으면 해당노드를 반환하고, 데이터를 찾지 못했으면 모든 노드의 마지막까지 접근했으므로 null을 반환한다.

기존노드를 찾았으면 새노드의 next 프로퍼티를 기존노드의 next프로퍼티 값으로 설정한다. 그리고 기존노드의 next프로퍼티를 새노드의 next프로퍼티로 설정한다. 다음은 insert()함수를 구현한코드다.

LList.prototype.insert = function(newElement, item){
    var newNode = new Node(newElement);
    var current = this.find(item);
    //새로만든 노드의 next에 current.next를 넣는다.
    //current.next가 이 리스트의 마지막 값일 경우는 null이다.
    newNode.next = current.next;
    //current.next를 newNode.next에 넣어줬으므로
    //currnet.next에는 새로만든노드인 newNode를 넣는다.
    current.next = newNode;
}

이제 연결 리스트 코드를 테스트할 수 있다. 하지만 그 전에 연결리스트의 요소를 출력할 display()함수가 필요하다.

LList.prototype.display = function(){
    var currNode = this.head;
    //currNode의 다음 노드의 element만 접근한다.
    while(!(currNode.next == null)){
        console.log(currNode.next.element);
        currNode = currNode.next;
    }
}

display함수는 currNode에 헤드를 할당하면서 연결리스트 탐색을 준비한다. 현재노드의 next프로퍼티가 null이 아니면 탐색을 반복한다.

실제로 데이터를 포함하는 노드만 출력할수있도록(즉, 헤드노드는 제외하도록) currNode가 가리키는 다음 노드의 element 프로퍼티만 접근한다.

연결리스트에서 노드 삭제하기

연결리스트에서 노드를 삭제하려면 삭제하려는 바로 이전노드를 찾아 next프로퍼티를 삭제하려는 노드의 다음노드로 설정해야한다. 이전노드를 찾는findPrevious()하는 함수를 정의할것이다. 이함수는 연결리스트를 탐색하다가, 다음노드에서 삭제하려는 데이터를 포함하고 있으면 탐색을 멈춘다. 삭제하려는 데이터를 찾았으면 삭제하려는 데이터를 포함하는 노드의 이전노드를 반환한다. 그래야만 이전 노드의 next프로퍼티를 고칠 수 있기 때문이다.

LList.prototype.findPrevious = function(item){
    var currNode = this.head;
    //마지막 값도 아니고, item값이 currNode의 다음값이 아닐경우
    //currNode를 다음값으로 변경한다.
    while(!(currNode.next == null) && (currNode.next.element != item)){
        currNode = currNode.next;
    }
    return currNode;
}

이제 remove()함수를 구현한다.

LList.prototype.remove = function(item){
    var prevNode = this.findPrevious(item);
    if(!(prevNode.next == null)){
        //이전노드의 다음값을 다음의 다음값으로
        prevNode.next = prevNode.next.next;
    }
}

양방향 연결 리스트

지금까지 살펴본 것처럼 연결 리스트의 첫번째 노드에서 마지막 노드까지 쉽게 탐색 할 수 있었다. 하지만 역방향으로 노드르 탐색하는것은 쉽지 않다. 노드에 이전 노드의 링크를 저장하는 프로퍼티를 추가하면 이문제를 쉽게 해결할 수 있다. 하지만 링크를 하나 더 추가하면 리스트에 노드를 추가할때 더 많은 작업을 해야한다. 대신 리스트의 노드를 삭제할 때는 더이상 이전 노드를 찾을 필요없으므로 삭제과정은 좀더 간단해진다.

function Node(element){
    this.element = element;
    this.next = null;
    this.previous = null;
}

양방향 리스트의 insert()함수는 새노드의 previous프로퍼티를 이전 노드로 설정해야 한다.

LList.prototype.insert = function(newElement, item){
    var newNode = newNode(newElement);
    var currnet = this.find(item);
    newNode.next = current.next;
    newNode.previous = current;
    current.next = newNode;
}

양방향 연결 리스트의 remove()함수에서는 이전 노드를 찾을 필요가 없으므로(현재 노드의 previous값이 있다.) 단방향 연결 리스트의 삭제 함수보다 간단하다.

LList.prototype.remove = function(item){
    var currNode = this.find(item);
    if(currNode.next != null){
        currNode.previous.next = currNode.next;
        currNode.next.previous = currNode.previous;
        currNode.previous = null;
        currNode.next = null;    
    }else{
        currNode.previous.next = null;
        currNode.previous = null;
        currNode.next = null;    
    }
}

양방향 연결리스트는 마지막 노드로 이동하는 유틸리티 함수 findLast()를 이용해 역순으로 연결리스트를 출력하는 동작 dispReverse()을 수행할 수 있다.

LList.prototype.findLast = function(){
    var currNode = this.head;
    while(currNode.next != null){
        currNode = currNode.next;
    }
    return currNode;
}

LList.prototype.dispReverse = function(){
    var currNode = this.head;
    currNode = this.findLast();

    while(currNode.previous != null){
        console.log(currNode.element);
        currNode = currNode.previous;
    }
}

순환형 연결 리스트

순환형 연결리스트는 단방향 연겨리스트와 같은 종류의 노드를 포함한다. 유일하게 다른점은 순환형 연결리스트에서는 헤드의 next프로퍼티가 자신을 가르킨다는 것이다.

head.next = head

이 동작이 전체리스트에 적용되어 항상 마지막 노드의 next프로퍼티는 헤더를 가리킨다.

header --> apple --> banana --> coconut 
  └────────────────────────────────┘

복잡한 양방향 연결리스트를 만들지 않고도 간단하게 역방향 탐색이 가능하다는 것이 순환형 연결리스트이 강점이다. 순환형 연결리스트에서는 노드의 끝을 지나 계속탐색하면 결국 역방향에 있는 노드로 이동할 수 있다.

function LList(){
    this.head = new Node("head");
    this.head.next = this.head;
    this.find = find;

}

LList.prototype.display = function(){
    var currNode = this.head;
    //currNode의 다음 노드의 element만 접근한다.
    while((currNode.next != null) && (currNode.next.element != "head")){
        console.log(currNode.next.element);
        currNode = currNode.next;
    }
}

아니.. 이거 단단히 잘못됐음.

모든코드

function Node(element){
    this.element = element;
    this.next = null;
    this.previous = null;
}


function LList(){
    this.head = new Node("head");
}

LList.prototype.find = function(item){
    var currNode = this.head;
    //currNode.element가 item과 같은 값일때까지 될때
    //currNdoe.next를 계속 돌려서 저장한다.
    while(currNode.element != item){
        currNode = currNode.next;
    }
    return currNode;
}

LList.prototype.insert = function(newElement, item){
    var newNode = new Node(newElement);
    var current = this.find(item);
    //새로만든 노드의 next에 current.next를 넣는다.
    //current.next가 이 리스트의 마지막 값일 경우는 null이다.
    newNode.next = current.next;
    newNode.previous = current;
    //current.next를 newNode.next에 넣어줬으므로
    //currnet.next에는 새로만든노드인 newNode를 넣는다.
    current.next = newNode;
}

LList.prototype.display = function(){
    var currNode = this.head;
    //currNode의 다음 노드의 element만 접근한다.
    while(currNode.next != null){
        console.log(currNode.next.element);
        currNode = currNode.next;
    }
}

// LList.prototype.findPrevious = function(item){
//     var currNode = this.head;
//     while(!(currNode.next == null) && (currNode.next.element != item)){
//         currNode = currNode.next;
//     }
//     return currNode;
// }

LList.prototype.remove = function(item){
    var currNode = this.find(item);
    if(currNode.next != null){
        currNode.previous.next = currNode.next;
        currNode.next.previous = currNode.previous;
        currNode.previous = null;
        currNode.next = null;    
    }
}

LList.prototype.findLast = function(){
    var currNode = this.head;
    while(currNode.next != null){
        currNode = currNode.next;
    }
    return currNode;
}

LList.prototype.dispReverse = function(){
    var currNode = this.head;
    currNode = this.findLast();

    while(currNode.previous != null){
        console.log(currNode.element);
        currNode = currNode.previous;
    }
}


var cities = new LList();
cities.insert("apple","head");
cities.insert("banana","apple");
cities.display();
cities.remove("apple");
cities.display();
console.log(cities.head);
console.log(cities.find("banana").previous);
console.log(cities.find("head").next);
cities.dispReverse();