[자료구조] 연결리스트 (Linked List)

 연결리스트 (Linked List) 

큐(queue)에 해당하는 알고리즘 문제를 풀다가 시간 복잡도 문제를 해결하기 위해 연결리스트에 대해 공부해보았다.

---

 

1. 연결리스트란?

 연결리스트(Linked List) 는 index 번호를 사용하는 배열과 달리 연결(link)을 이용해 구현한 리스트를 말한다.

배열의 경우엔 아래처럼 index 번호로 값을 알 수 있다.

즉, index 번호와 값이 서로 연결되어 있다.

const arr = ['a', 'b', 'c'];
console.log(arr[1])  // index 1번의 값은 b

 

하지만 연결리스트는 각각의 값들이 서로 연결되어 있다.

아래의 사진을 보면, 10이라는 값에는 10이라는 data뿐만 아니라 10과 연결된 20의 주소(Link)까지도 담고 있다.

 

이때, 이 데이터 덩어리를 노드(Node)라고 하며, 노드는 노드의 값이 있는 Data Field와 다음 노드의 주소를 담고 있는 Link Field로 이루어져있다. 이때 연결리스트의 입구에 해당하는 첫 노드를 HEAD라 부르며, 마지막 노드를 TAIL이라 한다.

1. 노드(Node) : 연결리스트에서 하나의 데이터 단위
    - data field와 link field로 구성되어 있음
    - vertex(버텍스, 꼭지점의 의미)이라고 부르기도 함
2. Data Field : 노드의 값이 저장된 곳
    - value라는 변수 사용
3. Link Field : 다음 노드의 주소가 저장된 곳
    - next 변수 사용
4. HEAD : 첫 노드
5. TAIL : 마지막 노드
    - 마지막 노드 값은 null

const list = {
  head : {
    value : 10,
    next : {
      value : 20,
      next : {
        value : 30,
        next : {
          value : 40,
          next : null
        }
      }
    }
  }
}

 

728x90

 

---

2. 언제 쓰일까?

이러한 연결리스트는 웹 브라우저의 history를 관리할 때 사용한다.

여러 브라우저를 이동할 때, A라는 브라우저에서 B라는 브라우저를 열면 브라우저 방문 history에 각각의 방문 기록들이 연결리스트와 같은 자료구조로 저장되는 것이다.

또한, B라는 브라우저창으로 넘어갈 때 A의 방문기록도 함께 가지고 가기에 브라우저에서 앞으로 가기/뒤로가기가 가능한 것이다.

 

---

3. 장단점

3-1. 연결리스트의 장점

• 새로운 elements(node)를 삽입하고 삭제하는 것이 더 용이하다
• restructuring이 덜 복잡하다

3-2. 연결리스트의 단점

• 배열은 index로 바로 값을 찾을 수 있지만, 연결리스트는 그것이 불가능하므로 배열에 비해 특정 element(node)를 찾는 것이 비효율적이다
• 배열보다 더 많은 메모리를 사용한다

---

4. 구현

4-1. 기본 구조

연결리스트 노드는 데이터를 저장할 value 프로퍼티와 연결된 다음 노드의 주소를 저장할 next 프로퍼티로 이루어져있다.

아래에는 단일(단방향) 연결리스트이지만, 만약 이중(양방향) 연결리스트라면 앞의 노드를 가리키는 this.prev도 들어간다.

여기서는  단일 연결리스트(Singly Linked List) 로 코드를 살펴볼 것이다.

// 노드 클래스
class Node {
  constructor(value) {
    // 연결리스트의 TAIL이 null로 끝나기 때문에 next의 디폴트 값은 null이다
    this.value = value;
    this.next = null;
    // this.prev = null;
  }
}

// 단일 연결리스트
class LinkedList {
  constructor() {
    this.head = null;    // 첫 노드의 데이터가 없다면 null
    this.length = 0;     // 연결리스트의 크기(데이터 수)를 찾기 위한 프로퍼티, 디폴트값은 0
  }
}

 

---

4-2. 연결리스트에 노드 추가

노드는 기존의 노드의 맨 앞, 맨 뒤, 중간에 추가할 수 있다.

 

먼저, 연결리스트의 맨 앞(HEAD)에 노드를 추가하는 경우다.

이때 새로 생성된 노드의 주소(Link field, next)는 기존 노드의 HEAD와 연결되게 코드를 짜주면 된다.

그리고 노드가 추가 되었으니 리스트의 크기도 증가시켜준다.

addFirst(value) {
  const node = new Node(value);  // 새로운 노드 생성
  node.next = this.head;         // 새 노드의 끝(next) = 기존 첫 노드의 HEAD
  this.head = node;
  
  this.length++;                 // 리스트의 크기 +1
}

 

두번째는 연결리스트의 맨 뒤에 노드를 추가하는 경우다.

기존에 노드가 없다면 새로운 노드를 추가하는 것으로 끝내면 된다. 하지만 기존에 노드가 존재한다면, 현재 노드의 위치가 마지막 노드가 될 수 있도록 while문으로 옮겨주고, 그 다음 현재 노드(마지막 노드)의 끝에 새 노드를 추가해주면 된다.

addLast(value) {
  const node = new Node(value);
  let current;   // 현재 노드
  
  // 1. 기존 노드가 있을때
  if (this.head) {
    current = this.head;
    
    // 마지막 노드에 추가해야하므로, 현재 노드 위치가 마지막 노드가 될때까지 while문을 돌려준다
    while (current.next) {
      current = current.next;
    }
    current.next = node;  // 현재 노드의 끝에 새 노드 추가

  // 2. 기존 노드가 없을때
  } else {
    this.head = node;
  }
  
  this.length++;   // 리스크 크기 +1
}

 

마지막은 중간에 노드를 삽입하는 경우다.

일단 기존 노드의 범위에 들어가는 index인지 확인해야 하고, 이 index가 첫번째라면 맨 앞에 삽입하는 것처럼 해주면 된다.

중간에 삽입하는 경우라면, 삽입하는 index에 도달했을 때 양쪽 index의 노드들을 이전 노드와 다음 노드로 밀고 그 사이에 새 노드를 삽입해주면 된다.

addMiddle(value, index) {
  // 1. 기존 연결리스트의 범위를 벗어나는 index인 경우
  if (index > 0 && index > this.length) {
    return;
  }

  // 2. 첫 번째 노드라면
  if (index === 0) {
    const node = new Node(value);  // 새로운 노드 생성
    node.next = this.head;         // 새 노드의 끝(next) = 기존 첫 노드의 HEAD
    this.head = node;
    
    this.length++;                 // 리스트의 크기 +1
    return;
  }
  
  const node = new Node(value);
  let current, prev;
  
  // 현재 노드를 첫번째 노드로 설정
  current = this.head;
  let count = 0;
  
  while (count < index) {
    prev = current;          // 현재 노드를 이전 노드로 바꿈
    count++;
    current = current.next;  // 현재 노드를 다음 노드로 바꿈
  }
  node.next = current;       // 새로운 노드를 중간에 삽입함
  prev.next = node;
  
  this.length++;   // 리스트의 크기 +1
}

 

반응형

 

---

4-3. 연결리스트 노드 삭제

첫 번째는 연결리스트의 마지막 노드를 삭제하는 경우다.

removeLast() {
  let current = this.head;
  
  while (current.next.next !== null) {  // 2개 이상의 노드가 존재할 때
    current = current.next;  // 현재 노드를 다음 노드로 바꾸기
  }
  current.next = null;       // 다음 노드 제거
  
  this.length--;   // 리스트의 크기 -1
}

 

다음은 첫번째 노드와 중간의 노드를 삭제하는 경우다.

removeMiddle(value) {
  let current = this.head;
  let temp;

  if (current.value === value) {  // 첫 번째 노드를 삭제
    temp = current.next;
    current.next = null;
    this.head = temp;
    
  } else {
    while (current.next.value !== value) {  // 특정 노드 직전에 도달할 때까지 while문 돌리기
      current = current.next;
    }
    temp = current.next.next;   // 특정값 다음값을 저장
    current.next.next = null;
    current.next = temp;        // 특정값 직전값과 다음값을 연결
    
  }
  this.length--;  // 리스트의 크기 -1
}

 

---

5. 연결리스트 종류

연결리스트에는 단일 연결리스트(Singly Linked List) 외에도 좀 더 개선된 리스트들이 존재한다.

 

5-1. 이중 연결리스트 (Doubly Linked List)

• 뒤쪽 노드도 빠르게 탐색할 수 있도록 개선된 자료구조
• 특정 index를 탐색하고자 할 때, 해당 index가 중간보다 앞쪽인지 뒤쪽인지 판단하여 탐색한다
• 2개의 주소칸(Link Field)을 가진다
• 단점 : 주소칸이 2개나 필요하다

5-2. 원형 연결리스트 (Circular Linked List)

• 마지막 작업을 한 위치를 Head이자 Tail로 설정한 자료구조
• 굳이 Head와 Tail의 위치를 신경 쓸 필요가 없다
• 장점 : 마지막 위치에서 이어서 탐색, 삽입, 삭제 등을 곧바로 수행할 수 있다
• 단점 : 데이터 순서의 개념이 모호해지고, 그래서 index를 이용한 탐색이 어렵다

 

---

</> 끊임없이 성장하기 위해 공부한 내용을 글로 작성하고 있습니다. 틀린 부분이나 추가해야 할 부분이 있다면 언제든 댓글로 남겨주세요❗️

 

---

References

 

• https://dev.to/satishnaikawadi2001/build-a-linked-list-in-javascript-with-all-operations-4867
• https://opentutorials.org/module/1335/8821
• https://overcome-the-limits.tistory.com/16
• https://youtu.be/dvKuG3gfLFQ
• https://velog.io/@kimkevin90/Javascript를-이용한-Linked-List-구현