연결리스트의 시간복잡도

 

class LinkedList {
 length = 0;
  head = null;
 
  add(value) {
    if (this.head) { //head에 값이 있을때
      let current = this.head;
      while (current.next) {
        //다음이 없을때까지 계속 반복(다음이 없다는건 값이 비어있다는 것)
        current = current.next;
      }
      current.next = new Node(value); //current.next가 없을때 넣어준다
    } else { //head에 값이 없을때
      this.head = new Node(value); //그냥 해당 값을 추가하면된다
    }
    this.length++; //값이 들어갔으니깐 길이가 하나 길어진다
    return this.length; 
    //length값을 활용하기 위해 return 시킴
    (반환값을 value로 한다면 입력값이랑 동일하기 때문에 아무 의미가 없다)
  }
  
  search(index) {
    return this.#search(index)[1]?.value; //this.#search(index)[1]의 값은 current
  }
  
  #search(index) { //프라이빗 메서드를 사용
    let count = 0; //몇번 넘겼는지 카운트
    let prev;
    let current = this.head; //head가 값이 없을 수 있다
    while (count < index) {
      //주어진 index가 3이면 count는 0,1,2 3번 반복된다
      prev = current;
      current = current?.next;
      //optional chaining(옵셔널 체이닝)을 이용해 프로퍼티가 없는 중첩객체를
      //에러없이 안전하게 접근할수 있다.(null인 경우도 방어됨)
      count++;
    }
    return [prev, current];
  }
  //prev current current.next에서 current를 삭제하려면
  //사실 prev.next가 current로 되어있는 것을 current.next로 넣어주면 된다
  
  remove(index) {
    const [prev, current] = this.#search(index);
    if (prev && current) {
      //search(0)이면 prev가 undefined이고 prev.next를 할 수 없기때문에 prev가 있을때만 실행
      //head가 값이 없으면 current도 undefined이기 때문에 current가 있을때만 실행
      prev.next = current.next;
      this.length--;
      return this.length;
    } else if (current) {
      //index가 0 일때
      this.head = current.next;
      this.length--;
      return this.length;
    }
    //삭제하고자 하는 대상이 없을 때(prev, current가 둘다 없을 경우)
    //아무것도 안함
  }
}
const ll = new LinkedList(); //new LinkedList를 호출해 객체를 생성
ll.length;
ll.add(1); //1
ll.add(2); //2
ll.add(3); //3
ll.add(4); //4
ll.add(5); //5
ll.add(6); //6
ll.search(0); //1
ll.search(3); //4
ll.search(5); //6
ll.search(6); //undefined
ll.remove(4); //5를 지움
ll.remove(4); //5가 지워졌으니깐 6을 지움
ll.search(4); //undefined
ll.remove(4); //undefined

출처 : https://stopwon.tistory.com/6

Linked List (연결 리스트)

 

연결리스트의 시간 복잡도가 O(n)인 이유?

LinkedList 클래스의 시간 복잡도가 O(n)인 주된 이유는 add, search, remove 메서드에서 리스트의 노드를 순회하는 과정 때문입니다. 각 메서드의 동작 방식을 분석해보겠습니다.

add 메서드

• 새로운 값을 리스트에 추가할 때, 리스트의 끝에 도달할 때까지 현재 노드(current)에서 다음 노드(current.next)로 이동해야 합니다.
• 최악의 경우(리스트의 끝에 도달해야 할 때), 이 메서드는 리스트의 모든 노드를 한 번씩 방문해야 합니다.
• 따라서 add 메서드의 시간 복잡도는 리스트의 길이에 비례하여 증가하므로 O(n)입니다.

search 메서드

• 특정 인덱스의 노드를 찾기 위해, 리스트의 시작부터 해당 인덱스에 도달할 때까지 노드를 순회합니다.
• 최악의 경우, 찾고자 하는 노드가 리스트의 마지막에 위치하거나 리스트 내에 없는 경우, 리스트의 모든 노드를 방문해야 합니다.
• 이 과정도 리스트의 길이에 비례하여 시간이 소요되므로, search 메서드의 시간 복잡도는 O(n)입니다.

remove 메서드

• 특정 인덱스의 노드를 삭제하기 전에, 해당 노드를 찾기 위해 리스트를 순회합니다. 이는 search 메서드를 내부적으로 호출하는 과정과 유사합니다.
• 삭제할 노드의 위치를 찾기 위해서는 최악의 경우 리스트의 모든 노드를 방문해야 할 수 있습니다.
• 노드를 삭제하는 실제 작업은 O(1)의 시간이 걸리지만, 노드를 찾는 데에 O(n) 시간이 소요되므로, 전체 remove 메서드의 시간 복잡도는 O(n)입니다.

종합하면, LinkedList 클래스의 주요 메서드들이 리스트의 길이에 비례하는 시간이 소요되기 때문에 O(n)의 시간 복잡도를 가집니다. 이는 연결 리스트가 임의 접근이 불가능하고, 특정 요소에 접근하거나 수정, 삭제하기 위해선 순차적으로 노드를 순회해야 하기 때문입니다.

 

그렇다면 이 연결리스트의 시간복잡도를 O(1) 로 만드는 방법은 무엇일까요?

연결 리스트의 add, search, remove 메서드의 시간 복잡도를 O(1)로 바꾸는 것은 연결 리스트의 기본적인 특성과 제약 때문에 모든 경우에 가능하지 않습니다. 그러나 특정 조건이나 조작에 대해 시간 복잡도를 O(1)로 만들 수 있는 방법은 몇 가지 있습니다:

1. 끝에 추가하기 최적화: add 메서드의 경우

연결 리스트의 끝에 항목을 추가하는 작업의 시간 복잡도를 O(1)로 만들기 위해서는 리스트의 끝을 가리키는 tail 포인터를 유지하는 것이 효과적입니다. tail 포인터를 사용하면, 리스트의 마지막 요소에 즉시 접근할 수 있으므로, 새로운 노드를 추가할 때 리스트의 끝까지 순회할 필요가 없어집니다.

class LinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
    this.length = 0;
  }
 
  add(value) {
    const newNode = new Node(value);
    if (!this.head) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      this.tail.next = newNode;
      this.tail = newNode;
    }
    this.length++;
    return this.length;
  }
  // 나머지 메서드...
}
 

2. 특정 위치 조작 최적화

• 처음에 추가/삭제하기: 리스트의 시작 부분에 항목을 추가하거나 삭제하는 작업은 이미 O(1)의 시간 복잡도를 가집니다. head 포인터를 이용해 새 노드를 추가하거나 기존 노드를 제거하기 때문입니다.
• 특정 인덱스 검색: 일반적으로 search 메서드의 시간 복잡도를 O(1)로 만드는 것은 불가능합니다. 연결 리스트는 인덱스에 의한 직접 접근을 지원하지 않기 때문에, 특정 요소를 찾기 위해선 순차적으로 탐색해야 합니다.

3. 더블 링크드 리스트 사용

이중 연결 리스트를 사용하면, 리스트의 끝에서 시작하는 작업의 효율을 개선할 수 있습니다. tail 포인터와 함께 각 노드가 이전 노드를 가리키는 포인터를 추가로 유지함으로써, 리스트의 뒷부분에서도 O(1)에 접근할 수 있게 됩니다. 그러나 이 방법은 search 메서드의 일반적인 경우의 시간 복잡도를 O(1)로 만들지는 못합니다.

4. 해시 테이블과의 결합

특정 조건 하에서 연결 리스트의 요소를 빠르게 검색하고자 할 때, 해시 테이블을 사용하여 각 노드의 위치를 매핑할 수 있습니다. 이 방법은 검색, 추가, 삭제 연산을 O(1)의 시간 복잡도로 수행할 수 있게 해줍니다. 하지만 이는 추가적인 메모리 사용을 필요로 하며, 연결 리스트의 순차적 특성을 완전히는 활용하지 못하는 방식입니다.

결론적으로, 연결 리스트의 특정 연산에 대한 시간 복잡도를 O(1)로 개선할 수 있는 방법들이 있지만, 연결 리스트의 기본적인 성질과 제약 때문에 모든 연산을 O(1)로 만드는 것은 불가능합니다. 사용 사례에 따라 적절한 데이터 구조를 선택하는 것이 중요합니다.