연결리스트(Linked List)

연결리스트는, 각 노드가 데이터와 포인터를 갖고 한 줄로 연결되어 있는 형태로 데이터가 저장되는 자료구조이다.

연결 리스트의 종류로는 단일 연결 리스트, 이중 연결 리스트, 단순 원형 연결 리스트 등이 있다.

장점

기존의 배열에서 삽입 삭제 연산 시 이후의 모든 요소를 재배치해야 했던 것과 다르게, 연결리스트는 포인터만 수정해주면 된다.

때문에 시간복잡도가 O(1)이며, 배열보다 효율적인 연산이 가능해진다.

단점

데이터 검색에 O(n)만큼의 시간이 걸린다.

배열의 경우 인덱스가 존재하기 때문에, 이를 통해 즉각적으로 데이터를 검색할 수 있으나 연결 리스트는 모든 데이터를 순회해야 하기 때문에 시간이 오래 걸린다.

✅ 단일 연결 리스트

• 각 노드당 포인터가 하나씩 존재한다.
• 포인터는 다음 노드를 가리킨다.
• 테일 노드의 경우 포인터를 갖지 않는다.

✅ 이중 연결 리스트

• 각 노드당 포인터가 두 개씩 존재한다.
• 포인터는 양쪽 노드를 가리킨다.
• 테일 노드의 경우 하나의 포인터를 갖는다.

✅ 단순 원형 연결 리스트

• 단일 연결 리스트와 같은 특징을 갖는다.
• 이때, 테일 노드가 첫 번째 노드로의 포인터를 갖는다.

💻 자바스크립트 연결리스트 구현

기본 구조

//단일 연결리스트 노드 기본 구조
class Node {
  constructor(data) {
    this.pointer = null;
    this.data = data;
  }
}

//연결 리스트 기본 구조
class LinkedList {
  constructor() {
    this.head = null;
    this.count = 0;
  }
}

이번에 구현할 연결리스트는 단일 연결리스트이다.

만약 이중 연결리스트를 구현하고 싶다면, 생성자 하위에 이전 노드를 연결해주는 포인터를 추가한다.

원소 추가

맨 앞에 노드를 추가하는 경우

//맨 앞에 원소를 추가하는 경우
  insertHead(data) {
    const node = new Node(data);
    node.pointer = this.head;
    this.head = node;
    this.count++;
  }

맨 뒤에 노드를 추가하는 경우

  //맨 뒤에 원소를 추가하는 경우
  insertTail(data) {
    const node = new Node(data);
    let curNode = this.head;
    while (curNode.pointer !== null) {
      curNode = curNode.pointer;
    }
    curNode.pointer = node;
    this.count++;
  }

특정 위치에 노드를 추가하는 경우

  //리스트 중간에 원소를 추가하는 경우
  //index 번째에 data를 넣겠다
  insertAt(index, data) {
    const node = new Node(data);

    if (index === 0) {
      //리스트 처음에 원소를 삽입하려한다면
      this.insertHead(data);
      return;
    }
    if (index === this.size - 1) {
      //리스트 끝에 원소를 삽입하려 한다면
      this.insertTail(data);
      return;
    }
    if (index > this.size - 1) {
      //리스트 범위를 벗어나서 원소를 삽입하려 한다면
      console.log("범위를 벗어났습니다!");
      return;
    }

    //첫 번째 노드 | 인덱스까지 가기 위한 카운트 변수
    let curNode = this.head;
    let curCount = 0;

    while (curCount !== index - 1) {
      //첫 번째 노드부터 순회 시작하여, 인덱스 되기 전까지 반복
      curNode = curNode.pointer;
      curCount++;
    }

    let tmp = curNode.pointer; //기존 index 번째에 있던 노드
    node.pointer = tmp; //새로 추가할 노드의 포인터를 기존 index 번째에 있던 노드에 연결
    curNode.pointer = node; //i기존 index 직전 노드의 포인터를 새로 추가할 노드와 연결

    this.count++;
  }

원소 삭제

특정 위치의 노드를 삭제하는 경우

  //특정 위치에 있는 원소를 삭제하는 경우
  removeAt(index) {
    let curNode = this.head;
    let curCount = 0;
    let tmp;

    if (index === 0) {
      //첫 번째 노드를 삭제한다면
      tmp = curNode.pointer;
      curNode.pointer = null;
      this.pointer = tmp;
    } else {
      while (curCount !== index - 1) {
        //첫 번째 노드부터 순회 시작하여, 인덱스 되기 전까지 반복
        curNode = curNode.pointer;
        curCount++;
      }
      tmp = curNode.pointer.pointer; //삭제될 노드의 다음 다음 노드
      curNode.pointer.pointer = null; //연결 끊기
      curNode.pointer = tmp;
    }
    this.count--;
  }

테일 노드를 삭제하는 경우

  //마지막 노드를 삭제하는 경우
  removeTail() {
    if (this.count === 1) {
      this.removeAt(0);
      return;
    }
    if (this.count < 1) {
      return;
    }
    let curNode = this.head;
    while (curNode.pointer.pointer !== null) {
      //노드의 다음 다음 노드가 null이면, 다음 노드가 Tail 노드라는 것을 알 수 있기 때문.
      curNode = curNode.pointer;
    }
    curNode.pointer = null;
    this.count--;
  }

테스트

  //출력용 메소드
  printListData() {
    let current = this.head;

    while (current) {
      console.log(current.data);
      current = current.pointer;
    }
  }

💙 전체코드

//단일 연결리스트 노드 기본 구조
class Node {
  constructor(data) {
    this.pointer = null;
    this.data = data;
  }
}

//연결 리스트 기본 구조
class LinkedList {
  constructor() {
    this.head = null;
    this.count = 0;
  }

  //맨 앞에 원소를 추가하는 경우
  insertHead(data) {
    const node = new Node(data);
    node.pointer = this.head;
    this.head = node;
    this.count++;
  }

  //맨 뒤에 원소를 추가하는 경우
  insertTail(data) {
    const node = new Node(data);
    let curNode = this.head;
    while (curNode.pointer !== null) {
      curNode = curNode.pointer;
    }
    curNode.pointer = node;
    this.count++;
  }

  //리스트 중간에 원소를 추가하는 경우
  //index 번째에 data를 넣겠다
  insertAt(index, data) {
    const node = new Node(data);

    if (index === 0) {
      //리스트 처음에 원소를 삽입하려한다면
      this.insertHead(data);
      return;
    }
    if (index === this.size - 1) {
      //리스트 끝에 원소를 삽입하려 한다면
      this.insertTail(data);
      return;
    }
    if (index > this.size - 1) {
      //리스트 범위를 벗어나서 원소를 삽입하려 한다면
      console.log("범위를 벗어났습니다!");
      return;
    }

    //첫 번째 노드 | 인덱스까지 가기 위한 카운트 변수
    let curNode = this.head;
    let curCount = 0;

    while (curCount !== index - 1) {
      //첫 번째 노드부터 순회 시작하여, 인덱스 되기 전까지 반복
      curNode = curNode.pointer;
      curCount++;
    }

    let tmp = curNode.pointer; //기존 index 번째에 있던 노드
    node.pointer = tmp; //새로 추가할 노드의 포인터를 기존 index 번째에 있던 노드에 연결
    curNode.pointer = node; //i기존 index 직전 노드의 포인터를 새로 추가할 노드와 연결

    this.count++;
  }

  //특정 위치에 있는 원소를 삭제하는 경우
  removeAt(index) {
    let curNode = this.head;
    let curCount = 0;
    let tmp;

    if (index === 0) {
      //첫 번째 노드를 삭제한다면
      tmp = curNode.pointer;
      curNode.pointer = null;
      this.pointer = tmp;
    } else {
      while (curCount !== index - 1) {
        //첫 번째 노드부터 순회 시작하여, 인덱스 되기 전까지 반복
        curNode = curNode.pointer;
        curCount++;
      }
      tmp = curNode.pointer.pointer; //삭제될 노드의 다음 다음 노드
      curNode.pointer.pointer = null; //연결 끊기
      curNode.pointer = tmp;
    }
    this.count--;
  }

  //마지막 노드를 삭제하는 경우
  removeTail() {
    if (this.count === 1) {
      this.removeAt(0);
      return;
    }
    if (this.count < 1) {
      return;
    }
    let curNode = this.head;
    while (curNode.pointer.pointer !== null) {
      //노드의 다음 다음 노드가 null이면, 다음 노드가 Tail 노드라는 것을 알 수 있기 때문.
      curNode = curNode.pointer;
    }
    curNode.pointer = null;
    this.count--;
  }

  //출력용 메소드
  printListData() {
    let current = this.head;

    while (current) {
      console.log(current.data);
      current = current.pointer;
    }
  }
}

const linkedList = new LinkedList();
linkedList.insertHead(1234);
linkedList.insertTail(6789);
linkedList.insertTail(351);
linkedList.insertTail(5457);
linkedList.insertTail(57864163);
linkedList.insertAt(1, 666666666);
linkedList.removeAt(1);
linkedList.removeTail();
linkedList.removeTail();
linkedList.printListData();

Reference

[Data Structure] 연결리스트에 대해 알아보자(Linked List)

위키피디아 연결리스트

자바스크립트로 연결 리스트(Linked List) 구현하기