[자바스크립트] LinkedList 연결 리스트 클래스

Linked List 클래스

연결 리스트란?

연결 리스트는 각 데이터들을 포인터로 연결하여 관리하는 자료구조입니다.

연결 리스트에서는 노드라는 새로운 개념이 나오는데, 각 노드는 데이터를 저장하는 데이터 영역과 다음 데이터가 저장된 노드를 가리키는 포인터 영역으로 구성됩니다.

연결 리스트의 데이터 삽입

데이터를 생성한 뒤 기존 연결들의 연결관계를 조정해서 삽입합니다.

아래 그림처럼 [1,3,5] 의 리스트 에 [2] 를 삽입해서 [1,2,3,5] 리스트를 만들고 싶은 경우

1단계. 2가 3을 가리키게 합니다.

2단계. 1이 2를 가리키게 합니다.

[1,2,3,5] 리스트 완성입니다.

연결 리스트의 데이터 삭제

데이터 자체를 삭제하는 개념이 아닌 데이터끼리 가리키는 곳(포인터)를 활용해서 아무도 가리키지 않게 만들어 삭제와 같은 효과를 줄 수 있습니다. (보통 가비지 콜렉션에 의해 데이터는 결국 삭제되는 것으로 알고있습니다.)

아래의 그림같이 [1,3,5] 리스트에서 [3] 을 삭제해서 [1,5] 리스트를 만들고 싶은 경우

1이 3을 가리키면 됩니다.

아무도 3을 가리키지 않기 때문에 3에 접근할 수가 없어 의미가 없어진 3을 빼고 보면 아래와 같습니다.

[1,5] 리스트 완성입니다.

자바스크립트로 다음과 같은 기능을 가진 연결 리스트를 구현해 보겠습니다.

Node 클래스

변수	설명
element	요소가 저장되는 변수입니다.
next	다음 노드를 저장하는 변수입니다.

LinkedList 클래스

변수	설명
head	Node 객체가 저장됩니다.

함수	설명
find(item)	item 을 element로 갖는 node를 찾기
findPrevious(item)	item 을 element로 갖는 node를 가리키는 node를 찾기
append(newElement)	newElement 를 element로 갖는 node를 뒤에 추가
insert(newElement, item)	item 을 element로 갖는 node 뒤에 newElement 를 element로 갖는 node를 추가
remove(item)	item 을 element로 갖는 node를 삭제
toString()	연결 리스트의 요소들을 출력

연결 리스트 구현 코드입니다.

// node 구현
function Node(element) {
    this.element = element;
    this.next = null;
}
 
// Linked List 구현
function LinkedList() {
    this.head = new Node("head");
    this.find = find;
    this.append = append;
    this.insert = insert;
    this.remove = remove;
    this.toString = toString;
    this.findPrevious = findPrevious;
}
 
// 노드 찾기
function find(item) {
    var currNode = this.head;
    while(currNode.element != item) {
        currNode = currNode.next;
    }
    return currNode;
}
 
// 이전 노드 찾기
function findPrevious(item) {
    var currNode = this.head;
    while(currNode.next != null && currNode.next.element != item) {
        currNode = currNode.next;
    }
    return currNode;
}
 
// 노드 추가
function append(newElement) {
    var newNode = new Node(newElement); //새로운 노드 생성
    var current = this.head; // 시작 노드
    while(current.next != null) { // 맨 끝 노드 찾기
        current = current.next;
    }
    current.next = newNode;
}
 
// 노드 중간 삽입
function insert(newElement, item) {
    var newNode = new Node(newElement); //새로운 노드 생성
    var current = this.find(item); // 삽입할 위치의 노드 찾기
    newNode.next = current.next; // 찾은 노드가 가리키는 노드를 새로은 노드가 가리키기
    current.next = newNode; // 찾은 노드는 이제부터 새로운 노드를 가리키도록 하기
}
 
// 노드 삭제
function remove(item) {
    var preNode = this.findPrevious(item); // 삭제할 노드를 가리키는 노드 찾기
    preNode.next = preNode.next.next; // 삭제할 노드 다음 노드를 가리키도록 하기
}
 
// 연결 리스트의 요소들을 출력
function toString() {
    var str = '[ ';
    var currNode = this.head;
    while(currNode.next != null){
        str += currNode.next.element+' ';
        currNode = currNode.next;
    }
    return str+']';
}

연결 리스트 간단한 사용 예제입니다.

var linkedList = new LinkedList();
linkedList.insert("A", "head");
linkedList.insert("B", "A");
linkedList.insert("C", "B");
linkedList.remove("B");
linkedList.append("D");
linkedList.append("E");
alert(linkedList.toString());