자료구조 - 연결 리스트

연결 리스트는 배열과 마찬가지로 항목의 리스트를 표현하는 자료 구조다. 

메모리에 곳곳에 흩어진 연결된 데이터를 노드라고 부르고, 각 노드는 다음 노드의 메모리 주소도 포함한다. 이를 링크라고 한다. 

 

노드와 연결리스트를 직접 코드로 구현해봤다. 여기서 length는 노드의 개수이고, head는 첫 노드의 주소이다. 

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

class LinkedList {
  length = 0;
  head = null;    
}

 

데이터를 추가, 검색, 삭제하는 메소드도 추가로 구현해보았다. 

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

class LinkedList {
  length = 0;
  head = null;

  add(value) {
    const node = new Node(value);
    let current = this.head;
    if (!current) { // 현재 아무 노드도 없으면
      this.head = node; // head에 새 노드를 추가합니다.
      this.length++;
      return node;
    } else { // 이미 노드가 있으면
      while (current.next) { // 마지막 노드를 찾고.
        current = current.next;
      }
      current.next = node; // 마지막 위치에 노드를 추가합니다.
      this.length++;
      return node;
    }
  }
  
  search(position) {
    let current = this.head;
    let count = 0;
    while (count < position) { // position 위치만큼 이동합니다.
      current = current.next;
      count++;
    }
    return current?.data; // data가 없으면 undefined
  }
  
  remove(position) {
    let current = this.head;
    let before;
    let remove;
    let count = 0;
    if (position == 0) { // 맨 처음 노드를 삭제하면
      remove = this.head;
      this.head = this.head.next; // head를 두 번째 노드로 교체
      this.length--;
      return remove;
    }
    // 그 외의 다른 노드를 삭제하면
    while (count < position) {
      before = current;
      count++;
      current = current.next;
    }
    remove = current;
    before.next = remove.next;
    // remove 메모리 정리
    this.length--;
    return remove;
  }
}

위는 한 쪽 방향으로만 이동하는 연결 리스트이기 때문에 뒤로 가기는 불편하다. 

이걸 해결한 리스트가 바로 이중 연결 리스트이다. 다음 노드를 가리키는 next 외의 this.prev를 넣어 이전 노드를 가리키도록 해주면 된다. 

 

또한 위는 하나의 데이터씩만 연결되어 있지만 한 노드에서 여러 노드를 연결하는 다중 연결 리스트도 있다. 

this.next를 노드들의 배열로 만들면 된다. 

 

시간복잡도

---

• 맨 앞 추가 => O(1)
• 맨 뒤 추가 => O(n)
• 검색 => O(n)
• 맨 앞 삭제 => O(1)
• 맨 뒤 삭제 => O(n)

 

연결 리스트가 배열보다 강력한 장점을 보이는 연산은 바로 맨 앞에 삽입, 삭제하는 경우이다.

맨 앞에 데이터를 추가, 삭제할 때 배열의 경우 O(n)의 시간복잡도가 소요되지만, 연결 리스트의 경우 O(1)의 시간 복잡도가 소요되기 때문이다. 

 

배열과 연결 리스트 비교

---

연산	배열	연결 리스트
읽기	O(1)	O(n)
검색	O(n)	O(n)
삽입	O(n) - 끝에서는 O(1)	O(n) - 앞에서는 O(1)
삭제	O(n) - 끝에서는 O(1)	O(n) - 앞에서는 O(1)

 

참고자료

---

• 제로초 블로그
• 백준 문제 모음
• 유튜브

 

---

질문이나 잘못된 점은 댓글로 남겨주세요 :)💖