[2023-09-22] TIL - 연결리스트(Linked List), JS

추가와 삭제가 반복되는 로직이라면 어떻게 해야할까?

 

바로 연결리스트를 사용하면 된다.

 

 

연결리스트

- 연결리스트는 각요소를 포인터로 연결하여 관리하는 선형 자료구조이다.

- 각 요소는 노드라고 부르며 데이터 영역과 포인터 영역으로 구성된다.

출처 : 나무위키

연결리스트의 특징

- 메모리가 허용하는 한요소를 제한없이 추가할 수 있다.

- 탐색은 O(n)dl 소요된다.

- 요소를 추가하거나 제거할 때는 O(1)이 소요된다.

- Singly Linked List, Doubly Linked List, Circular Linked List가 존재한다.

 

 

배열과의 차이점

메모리차이

- 배열은 순차적인 데이터가 들어가므로 메모리 영역을 연속적으로 사용한다.

- 연결리스트는 순차적이지 않기 때문에 각 데이터가 퍼져있다.

- 연결리스트는 퍼져있는 메모리 영역을 알기위해 포인터를 사용하여 각 영역을 참조한다.

 

 

요스를 추가, 삭제에서의 시간복잡도 차이

-배열은 요소를 추가하거나 삭제할 때 시간복잡도 O(n)이 걸린다.

- 반면에 연결리스트의 추가, 삭제는 상수 시간 O(1)만 소요가 된다.

 

Singly Linked List

- 가장 기본적이고 단순한 연결리스트

- Head에서 Tail까지 단방향으로 이어지는 연결리스트

핵심 로직

-요소 찾기

1. 헤드 포인터부터 시작하여 다음요소인 헤드를 찾는다

2. 해당요소가 우리가 찾는 요소인지 확인하고 아니라면 다음요소로 넘어간다.

3. 이를 반복하여 찾는다.

 -O(N) 시간이 걸린다.

 

- 요소 추가 

1. 추가할 요소의 포인터를 추가할 영역의 다음 요소를 가리키게 한다.

2. 이어서 추가할 영역의 이전 요소는 추가할 요소를 가리키게한다.

 -O(1)인 상수시간이 소요된다. -> 하지만 추가할 요소를 탐색하고 추가하기때문에 O(N)이 걸린다.

 - 즉 추가하는 동작만 상수시간이 소요됨

 - 추가를 위한 탐색을 하지않도록 주의해야한다.

 

- 요소 삭제

1. 삭제할 요소의 이전요소가 삭제할 요소의 다음요소를 가리키게한다.

2. 그리고 삭제할요소를 완전히 삭제한다.

 -O(1)인 상수시간이 소요된다.

 

 

단일 연결리스트 자바스크립에서 구현

// node 구현
class Node {
  constructor(element) {
    this.element = element;
    this.next = null;
  }
}
// Linked List 구현
class LinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
    this.size = 0;
  }

  // 노드 찾기
  find(item) {
    let currNode = this.head;

    while (currNode.element != item) {
      currNode = currNode.next;
      if (currNode == null) {
        return false;
      }
    }
    return currNode;
  }

  // 이전 노드 찾기
  findPrevious(item) {
    let currNode = this.head;
    if (currNode.element === item) return false;
    while (currNode.next != null && currNode.next.element != item) {
      currNode = currNode.next;
    }
    return currNode;
  }

  // 노드 추가
  append(newElement) {
    let newNode = new Node(newElement);
    if (this.head === null) {
      this.head = newNode;
    } else {
      this.tail.next = newNode;
    }
    this.tail = newNode;
    this.size++;
  }

  // 노드 중간 삽입
  insert(newElement, item) {
    let newNode = new Node(newElement);

    if (!this.head) {
      this.head = newNode;
      this.tail = newNode;
      this.size++;
      return;
    }
    //삽입하려는 위치가 헤드일 경우
    if (this.head.element === item) {
      newNode.next = this.head;
      this.head = newNode;
      this.size++;
      return;
    }

    let currNode = find(item);
    if (currNode) {
      newNode.next = currNode.next;
      currNode.next = newNode;
      if (!newNode.next) {
        //만약 새로 추가한 요소가 꼬리 위치였다면
        this.tail = newNode;
      }
      this.size++;
    } else {
      console.log("리스트에 해당되는 요소가 없어 삽입을 실행할 수 없습니다.");
    }
  }

  remove(item) {
    if (!this.head) {
      console.log("리스트가 비어 있습니다.");
      return;
    }

    // 리스트에 요소가 하나만 있을 때 꼬리를 업데이트
    if (this.head.element === item) {
      this.head = this.head.next;
      if (!this.head) {
        this.tail = null;
      }
      this.size--;
      return;
    }

    let currNode = this.find(item);
    let prevNode = this.findPrevious(currNode.element);

    if (currNode) {
      prevNode.next = currNode.next;
      if (!currNode.next) {
        //만약 삭제한 요소가 꼬리 위치였다면
        this.tail = prevNode;
      }
      this.size--;
    } else {
      console.log("리스트에 해당하는 요소가 없어 제거를 실행할 수 없습니다.");
    }
  }
  // 연결 리스트의 요소들을 출력
  display() {
    let str = "[ ";
    if (!this.head) {
      console.log("리스트가 비어 있습니다.");
      return tr + "]";
    }
    let currNode = this.head;
    while (currNode !== null) {
      str += currNode.element + ", ";
      currNode = currNode.next;
    }
    return str + "]";
  }

  // 연결리스트 크기 반환
  getSize() {
    return this.size;
  }
}
const linkedList = new LinkedList();
linkedList.append("3431111");
linkedList.insert("1", "3431111");
linkedList.append("34321");
linkedList.remove("3431111");
console.log(linkedList.display());
console.log(linkedList.getSize());

 

이해가 잘 안돼서 그림으로 한번 그려보았다.

 

Append 실행 시

1. 처음에는 Head와 Tail에 노드가 들어간다.

2. 두 번째 append 시 tail.next로 tail안에 있던 노드의 next를 B로 설정해준다.

그렇게 되면 Head에 있던 노드도 같은 노드이므로 같이 바뀌게 된다. 

-> 즉 노드는 상태가 공유된다.

3. 그리고 tail에 newNode가 들어오게 된다.

4.  한 번더 newNode를 Append하면 다시 newNode가 tail.next로 들어가서 B 노드의 next를 바꿔준다.

5. 그리고 tail에는 C 노드가 들어가게 된다.

그리고 아래와 같은 연결상태가 된다.

그림을 그려보면서 이해한 점은

Head나 Tail에 저장된 노드의 정보를 이용해서 먼저 노드를 찾고,

찾은 노드의 연결 포인터인 next에 추가할 노드의 정보를 넣는다.

-> 추가할 노드의 정보를 넣음으로써 서로 연결됨을 뜻하게 된다.

만약 삭제하거나 삽입하려고 한다면 head에 저장된 노드를 이용해서 순차적으로 노드를 탐색한다.

-> 즉 A 노드에 연결된 B 노드를 탐색하고, B 노드에 연결된 C 노드를 탐색한다.

 

 

 

 

 

 

 

Doubly Linked List

- 양방향으로 이어지는 연결 리스트

- Singly Linked List보다 자료구조의 크기가 조금 더 크다.

 

이중 연결 리스트 코드

// node 구현
class Node {
  constructor(element) {
    this.element = element;
    this.next = null;
    this.prev = null;
  }
}

// Linked List 구현
class LinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
    this.size = 0;
  }

  // 노드 찾기
  find(item) {
    let currNode = this.head;

    while (currNode.element != item) {
      currNode = currNode.next;
      if (currNode == null) {
        return false;
      }
    }
    return currNode;
  }

  // 노드 추가
  append(newElement) {
    let newNode = new Node(newElement);

    if (!this.head) {
      this.head = newNode;
    } else {
      newNode.prev = this.tail;
      this.tail.next = newNode;
    }
    this.tail = newNode;
    this.size++;

    return newNode;
  }

  // 노드 중간 삽입
  insert(newElement, item) {
    let newNode = new Node(newElement);

    //리스트가 비어있을 때
    if (!this.head) {
      this.head = newNode;
      this.tail = newNode;
      return;
    }

    let currNode = this.find(item);
    if (currNode) {
      if (currNode === this.head) {
        //삽입하려는 위치가 헤드 위치 다음이라면
        newNode.next = this.head;
        this.head.prev = newNode;
        this.head = newNode;
      } else {
        // 그 외 위치라면
        newNode.prev = currNode.prev;
        newNode.next = currNode;
        currNode.prev.next = newNode;
        currNode.prev = newNode;
      }
      this.size++;
    } else {
      console.log("리스트에 해당되는 요소가 없어 삽입을 실행할 수 없습니다.");
    }
  }

  // 노드 삭제
  remove(item) {
    if (!this.head) {
      console.log("리스트가 비어 있습니다.");
      return;
    }

    let currNode = this.find(item);
    //예외 처리 - 찾는요소가 있을 떄
    if (currNode) {
      if (currNode === this.head && currNode === this.tail) {
        //만약 삭제하는 요소가 리스트에서 단 하나라면
        this.head = null;
        this.tail = null;
      } else if (currNode === this.head) {
        //삭제하는 요소가 헤드 요소라면
        this.head = this.head.next;
        this.head.prev = null;
      } else if (currNode === this.tail) {
        //삭제하는 요소가 테일 요소라면
        this.tail = this.tail.prev;
        this.tail.next = null;
      } else {
        // 그 외 요소라면
        currNode.prev.next = currNode.next;
        currNode.next.prev = currNode.prev;
      }
    } else {
      console.log("리스트에 해당하는 요소가 없어 제거를 실행할 수 업습니다.");
    }

    this.size--;
  }

  // 연결 리스트의 요소들을 출력
  display() {
    let str = "[ ";
    if (!this.head) {
      console.log("리스트가 비어 있습니다.");
      return (str = "[ ");
    }

    let currNode = this.head;
    while (currNode != null) {
      str += currNode.element + ", ";
      currNode = currNode.next;
    }
    return str + "]";
  }

  // 연결리스트 크기 반환
  getSize() {
    return this.size;
  }
}

const linkedList = new LinkedList();
linkedList.append("343");
linkedList.insert("1", "343");
linkedList.append("3431121");
linkedList.remove("34311");
console.log(linkedList.display());
console.log(linkedList.getSize());

백준 연결리스트 문제

https://ydoag2003.tistory.com/225

[JS] 백준 2164 : 카드2 - 큐, 스택, 링크드리스트(push,pop의 비효율)

 

 

Circular Linked List

- Singly 혹은 Doubly Linked List에서 Tail이 Head로 연결되는 연결리스트

- 메모리를 아껴쓸 수 있다. 원형 큐 등을 만들 때도 사용된다.

 

 

원형 연결리스트 코드

// node 구현
class Node {
  constructor(element) {
    this.element = element;
    this.next = null;
  }
}

// Linked List 구현
class LinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
    this.size = 0;
  }

  // 노드 찾기
  find(item) {
    let currNode = this.head;
    while (currNode.element != item) {
      currNode = currNode.next;
      //원형연결리스트는 currNode == this.head 조건 필요
      if (currNode == null || currNode == this.head) {
        return false;
      }
    }
    return currNode;
  }
  // 이전 노드 찾기
  findPrevious(item) {
    let currNode = this.head;
    if (currNode.element === item) return false;
    while (currNode.next != null && currNode.next.element != item) {
      currNode = currNode.next;
    }
    return currNode;
  }

  // 노드를 리스트의 끝에 추가하는 메서드
  append(item) {
    const newNode = new Node(item);

    if (!this.head) {
      this.head = newNode;
      this.tail = newNode;
      newNode.next = this.head;
    } else {
      this.tail.next = newNode;
      newNode.next = this.head;
      this.tail = newNode;
    }
    this.size++;
  }

  // 노드 중간 삽입
  insert(newElement, item) {
    const newNode = new Node(newElement);

    if (!this.head) {
      //빈 리스트일 때
      this.head = newNode;
      this.tail = newNode;
      newNode.next = this.head;
      return;
    }

    let currNode = this.find(item);
    let prevNode = this.findPrevious(currNode.element);
    if (currNode) {
      if (currNode === this.head) {
        //삽입하려는 위치가 헤드일 때
        newNode.next = this.head;
        this.head = newNode;
        this.tail.next = newNode;
      } else {
        // 그 외
        prevNode.next = newNode;
        newNode.next = currNode;
      }
      this.size++;
    } else {
      console.log("리스트에 해당하는 요소가 없어 삽입을 실행할 수 업습니다.");
    }
  }

  remove(item) {
    if (!this.head) {
      console.log("연결리스트가 비어 있습니다.");
      return;
    }

    let currNode = this.find(item);
    let prevNode = this.findPrevious(currNode.element);
    if (currNode) {
      if (currNode === this.head && currNode === this.tail) {
        //삭제하려는 요소가 리스트안에 하나밖에 없을 때
        this.head = null;
        this.tail = null;
      } else if (currNode === this.head) {
        //삭제하려는 요소가 헤드 요소일 떄
        this.head = this.head.next;
        this.tail.next = this.head;
      } else if (currNode === this.tail) {
        //삭제하려는 요소가 테일 요소일 떄
        this.tail = prevNode;
        this.tail.next = this.head;
      } else {
        //삭제하려는 요소가 중간 요소일 때
        prevNode.next = currNode.next;
      }
    } else {
      console.log("리스트에 해당하는 요소가 없어 제거를 실행할 수 업습니다.");
    }
  }

  // 연결 리스트의 요소들을 출력
  display() {
    let str = "[ ";
    if (!this.head) {
      console.log("연결리스트가 비어 있습니다.");
      return str + "]";
    }
    let currNode = this.head;
    while (currNode.next !== this.head) {
      str += currNode.element + ", ";
      currNode = currNode.next;
    }
    str += currNode.element + " ";

    return str + "]";
  }

  // 연결리스트 크기 반환
  getSize() {
    return this.size;
  }
}

const linkedList = new LinkedList();
linkedList.append("8");
linkedList.remove("8");

console.log(linkedList.display());