자바스크립트 자료구조 연결 리스트(Linked List)

리스트 자료구조는 데이터를 나란히 저장하며, 중복된 데이터의 저장을 막지 않는다.

리스트는 수학적으로 중복을 허용하지 않는 '집합'과 다르다.

리스트라는 자료구조는 구현방밥에 따라서 다음과 같이 크게 두가지로 나뉜다.

선형 리스트(Linear List): 배열을 기반으로 구현된 리스트(배열 리스트)

연결 리스트(Linked List): 노드의 연결로 구현된 리스트

---

배열 리스트(Array List)

배열은 가장 간단한 메모리 데이터 구조다. 거의 모든 프로그래밍 언어에서 배열은 기본으로 내장된 데이터 타입이다.

배열은 동일한 데이터 타입을 연속적으로 저장한 것이다.(물론 자바스크립트에서는 다른 타입의 데이터도 한 배열에 넣을 수 있다.)

 

배열 리스트의 장점

간단하고 사용하기 쉽다

데이터 참조가 쉽다. 인덱스 값 기준으로 어디든 한번에 참조가 가능하다.

 

배열 리스트의 단점

고정된 크기: 배열의 크기가 초기에 결정되어야 한다, 변경이 불가능하다.(자바스크립트를 제외한 대부분의 언어에서는 그렇다.)

배열의 처음이나 중간에서 원소를 넣고 빼려면 비싼 연산을 빈번하게 수행한다.

---

연결 리스트(Linked List)

연결 리스트는 일련의 원소를 배열처럼 차례대로 저장하지만, 원소들이 메모리상에 연속적으로 위치하지 않는다는 점이 다르다.

다음과 같은 특징이 있다.

• 연속되는 항목들이 포인터로 연결된다.
• 마지막 항목은 Null을 가리킨다.
• 프로그램이 수행되는 동안 크기가 커지거나 작아질 수 있다.
• (시스템 메모리가 허용하는 한) 필요한 만큼 길어질 수 있다.
• 메모리 공안을 낭비하지 않는다.(하지만 포인터를 위한 추가의 메모리를 필요로 한다.)

배열에 비해 데이터의 추가/삽입 및 삭제가 용이하나 순차적으로 탐색하지 않으면 특정 위치의 요소에 접근할 수 없어 일반적으로 탐색 속도가 떨어진다.

즉 탐색 또는 정렬을 자주 하면 배열을, 추가/삭제가 많으면 연결 리스트를 사용하는 것이 유리하다. 

노드(Node)

연결 리스트에서 각 원소는 원소 자신과 다음 원소를 가리키는 포인터가 포함된 노드(Node)로 구성된다.

위 그림에서 보이듯이 '데이터를 저장할 장소'와 '다른 변수를 가리키기 위한 장소'가 구분되어 있다.

그래서 둘 이상의 Node가 연결된 상황은 아래와 같다.

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

연결 리스트 ADT

append(데이터): 리스트의 맨 끝에 데이터를 추가한다.

removeAt(위치): 해당 위치에 있는 데이터를 삭제한다.

indexOf(데이터): 해당 데이터의 인덱스를 반환한다. 존재하지 않을 경우 결과 값은 -1이다.

remove(데이터): 데이터를 삭제한다.

insert(위치, 데이터): 해당 위치에 데이터를 삽입한다.

isEmpty(): 데이터가 하나도 없다면 true를, 그 외엔 false를 반환한다.

size(): 데이터 개수를 반환한다. 배열의 length 프로퍼티와 비슷하다.

 

연결 리스트 만들기

일반적으로 연결 리스트는 단일 연결 리스트를 의미한다. 

단일 연결 리스트는 연결의 형태가 한쪽 방향으로 전개되고 시작과 끝이 분명히 존재한다. 

function LinkedList() {
    var _length = 0;
    var _head = null;
}

위에서 _length 프로퍼티는 연결 리스트에 담긴 데이터의 개수다.

눈여겨봐야 할 부분이 _head 프로퍼티로,  연결이 시작되는 지점을 참조한다.

연결 리스트끝에 데이터 삽입 append 메서드

연결 리스트의 끝에 데이터를 추가 할 때는 빈 연결 리스트인지 여부에 따라 두 가지 경우를 각각 고려해야 한다.

LinkedList.prototype.append = function(data) {
    var node = new Node(data);
    var curr;

    if( this._head == null ) {

        this._head = node;

    } else {
        curr = this._head;

        while( curr.next ) {
            curr = curr.next;
        }

        curr.next = node;
    }

    this._length ++;
};


var list = new LinkedList();
list.append(15);
list.append(10);

리스트가 처음부터 비어 있다면, _head 프로퍼티 값은 null 일 것이다.

_head가 null이면(리스트가 비어 있다면), _head가 새로 생성한 node를 가리키게 하면 된다.

리스트가 비어있지 않는 경우에는 리스트의 현재 node는 curr에 담아두고 next가 null이 되는 지점에서 루프를 끝낸다.

이때 curr이 바로 마지막 node이므로 curr.next가 새로 추가한 노드를 가리키게 하면 된다.

연결 리스트에서의 데이터 삭제

삭제하려는 데이터가 리스트의 첫 번째 데이터인지 아닌지에 따라 두 가지 경우를 생각해야 한다.

그래서 remove 메서드를, 데이터의 위치를 기준으로 삭제하는 메서드와 데이터의 값을 기준으로 삭제하는 메서드를 구현할 것이다.

데이터의 위치를 기준으로 삭제하는 removeAt

LinkedList.prototype.removeAt = function(pos) {
    if( pos > -1 && pos < this._length ) {
        var curr = this._head;
        var prev, index = 0;

        if( pos === 0 ) {
            this._head = curr.next;
        } else {
            while( index++ < pos ) {
                prev = curr;
                curr = prev.next;
            }

            prev.next = curr.next;
        }

        this._length --;

        curr.next = null;

        return curr.data;
    }

    return null;
};

삭제하려는 데이터가 리스트의 첫 번째 데이터인지 아닌지에 따라 두 가지 경우를 생각해야 한다.

 

데이터 값을 인자로 받아 리스트에서 해당 데이터의 인덱스를 반환하는 indexOf 메서드

LinkedList.prototype.indexOf = function(data) {
    var curr = this._head,
        index = -1;

    while( curr ) {
        if( curr.data === data ) {
            return index;
        }

        index ++;
        curr = curr.next;
    }

    return -1;
};

 

데이터 값을 기준으로 삭제하는 remove 메서드

LinkedList.prototype.remove = function(data) {
    var index = this.indexOf(data);
    return this.removeAt(index);
};

 

임의의 위치에 원소를 삽입 insert 메서드

LinkedList.prototype.insert = function(pos, data) {
    if( pos >= 0 && pos <= this._length ) {
        var node = new Node(data),
            curr = this._head,
            prev,
            index = 0;

        if( pos === 0 ) {
            node.next = curr;
            this._head = node;
        } else {
            while( index++ < pos ) {
                prev = curr;
                curr = curr.next;
            }

            node.next = curr;
            prev.next = node;
        }

        this._length ++;

        return true;
    }

    return false;
};

항상 인덱스가 개입되면 범위 체크는 필수다. 범위를 벗어낮다면 false를 반환하여 리스트에 아무것도 추가되지 않았을을 나타낸다.

여기서도 데이터를 맨 처음에 추가하는 경우와 리스트의 중간, 또는 맨 끝에 추가하는 경우 2가지로 나뉜다.

 

그 밖의 메서드

toString 메서드: 연결 리스트객체를 문자열로 변환한다.

LinkedList.prototype.toString = function() {
    var curr = this._head,
        str = '';

    while( curr ) {
        str += curr.data;
        curr = curr.next;
    }

    return str;
};

 

isEmpty 메서드: 리스트에 데이터가 하나라도 있으면 true를, 아니면 false를 반환한다.

LinkedList.prototype.isEmpty = function() {
    return this._length === 0;
};

 

size 메서드: 리스트의 크기를 반환한다.

LinkedList.prototype.size = function() {
    return this._length;
};

---

 

by 소년코딩

추천은 글쓴이에게 큰 도움이 됩니다.

악플보다 무서운 무플, 댓글은 블로그 운영에 큰 힘이됩니다.