공부를 위해 정리한 자료이므로 틀린 부분이 있을 수 있습니다. 그런 경우 댓글로 말씀해주시면 감사하겠습니다.

자료구조

• 자료구조 : 데이터의 표현 및 저장 방법
• 알고리즘 : 저장된 데이터를 처리하는 과정

즉, 자료구조를 알아야 알고리즘을 배울 수 있다.

연결 리스트(Linked List)

• 여러 개의 node로 이루어져 있는 리스트
• 노드는 데이터와 다음 노드의 주소로 구성되어 있음
• 데이터 추가/삭제/검색이 가능해야 함

단순 연결 리스트

• 다음 노드의 주소만을 가지는 연결 리스트
• 탐색 시 첫 노드에서부터 시작해서 최악의 경우 모든 노드를 검색해야하기 때문에, 시간 복잡도가 O(n)

이중 연결 리스트

• 다음 노드와 이전 노드의 주소를 가지는 연결 리스트
• 양방향 탐색 가능
• 이전 노드를 지정하기 위한 변수가 하나 더 필요하므로 메모리를 더 많이 사용
• 구현이 조금 더 복잡해짐

원형 연결 리스트

• 마지막 노드가 첫 번째 노드를 가리키게 하는 리스트

단순 연결 리스트 구현

zerocho님 블로그의 연결 리스트 구현 코드를 바탕으로 구현하였다.

• 마지막 노드의 주소를 가리키는 this.tail 추가
• add/addToTail/remove/search/contains 구현

let LinkedList = (function () {
    function LinkedList() {
        this.length = 0; // 노드의 개수
        this.head = null; // 첫 노드의 주소
        this.tail = null; // 마지막 노드의 주소
    }
    function Node(data) {
        this.data = data; // 데이터
        this.next = null; // 다음 노드의 주소
    }
  
    LinkedList.prototype.addToTail = function (value) { // 마지막 노드에 데이터 삽입
        let node = new Node(value);
        let current = this.tail;

        if (!current) { // 현재 아무 노드도 없으면
            this.head = node; // head에 새 노드를 추가
            this.tail = node; // tail에 새 노드를 추가
            this.length++;
            return node;
        } else { // 이미 노드가 있으면
            this.tail.next = node; // 마지막 노드의 next에 추가할 노드를 넣어준다.
            this.tail = node; // 추가할 노드를 tail로 설정한다.
            this.length++;
            return node;
        }
    };

    LinkedList.prototype.add = function (position, value) { // 데이터 삽입 (추가할 인덱스, 추가할 데이터)
        let current = this.head; // 첫 번째 노드
        let before;
        let node = new Node(value);
        let count = 0;

        if (position === 0) { // 맨 앞에 삽입할 경우
            node.next = this.head;
            this.head = node;
            this.length++;
            return node;
        }
      
        // 아닌 경우 position 찾기
        while (count < position) {
            before = current;
            count++;
            current = current.next;
        }

      	// 원래 가리키고 있던 다음 노드의 값을 변경
        node.next = before.next; // 이전 노드가 가리키는 주소를 추가할 노드의 다음 노드로 설정
        before.next = node; // 추가할 노드가 가리키는 주소를 원래 이전노드가 가리키던 노드 주소로 설정

        this.length++;
        return node;
    }

    LinkedList.prototype.search = function (position) {
        let current = this.head;
        let count = 0;

        if (position >= this.length) {
            return undefined;
        }
        if (count < position) {
            current = current.next;
            count++;
        }
        return current.data;
    };

    LinkedList.prototype.remove = function (position) {
        let current = this.head;
        let before;
        let remove;
        let count = 0;

        if (position === 0) { // 첫 번째 노드를 삭제하면
            remove = this.head;
            this.head = this.head.next; // this.nead를 두 번째 노드로 교체
            this.length--;
            return remove;
        } else { // 그 외 다른 노드를 삭제하면
            if (count < position) {
                before = current;
                count++;
                current = current.next;
            }
            remove = current; // 찾은 노드를 remove에 넣음
            before.next = remove.next; // 삭제할 노드의 다음 노드를 이전 노드의 next로 만들어 줌
            this.length--;
            return remove;
        }
    };

    LinkedList.prototype.contains = function (value) {
        let current = this.head;

        while (current) {
            if (current.data === value) {
                return true;
            }
            current = current.next;
        }
        return false;
    }
    return LinkedList;
})();


let list = new LinkedList();

list.addToTail(1);
list.addToTail(2);
list.addToTail(3);
list.addToTail(5);
console.log(list.length); // 4

list.add(3, 4);
list.addToTail(6);

console.log(list);
console.log(list.length); // 6
console.log(list.contains(7)); // false

위 코드의 결과

참조

자료구조(연결 리스트, linked list)