[자료구조] 연결리스트

1) 연결리스트란?

• 연속된 노드의 연결체

2) 노드(Node)란?

• 연결리스트에서 사용되는 하나의 데이터 덩어리이며, 데이터 & 링크 2가지 필드를 담고 있는 구조
• 그럼 노드의 구조는?
  • data : 노드가 담고 있는 데이터, 값
  • next : 링크 , 포인터 역활, 다음 노드의 주소를 저장

• 연결리스트의 구조는?
  - 연결리스트의 시작점에 있는 노드: head
  - 연결리스트의 마지막에 있는 노드: tail
  

3) 배열과 연결리스트의 차이

• random access 가능
  ⇒ 배열의 n번째 원소 방문시 O(1)
  시간으로 가능 예) arr[3]

• random access 불가능
  ⇒ 리스트의 n번째 노드 방문시 O(n)시간소요
  예) head 노드부터 n번째 노드까지 순회

• 원소 삽입 & 삭제 일반적으로 O(n) 시간 소요

• 배열보다 빨라질 수 있는 노드 삽입 & 삭제

4) 연결리스트의 종류는?

• 1) 단일 연결 리스트 (Singly Linked List)
  

• 2) 이중 연결 리스트 (Doubly Linked List)
  ⇒ 다음 노드, 이전노드를 가리키는 모든 포인터가 있어서 빠르지만 데이터의 구조와 흐름이 오히려 복잡해 질 수 있음

• 3) 원형 연결 리스트 (Circular Linked List)
  ⇒ 마지막 노드가 처음 노드를 카리키면서 원형 연결 노드가 완성된다.
  

5) 연결리스트 구현

const list = {
  head : {
    value : 90,
    next : {
      value : 10,
      next : {
        value : 89,
        next : {
          value : 100,
          next : null
        }
      }
    }
  }
}

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

class LinkedList {
  constructor() {
    let init = new Node("init")
    this.head = init;
    this.next = init;

    this.현재노드 = undefined;
    this.데이터수 = 0;
  }

  length() {
    return this.데이터수
  }

  append(date) {
    let 새로운노드 = new Node(data);
    this.tail.next = 새로운노드;
    this.tail = 새로운노드;
    this.데이터수 += 1; 
  }

  toString() {
    let 순회용현재노드 = this.head;
    순회용현재노드 = 순회용현재노드.next;

    let s ="";
    for (let i = 0; i < this.데이터수; i++){
      s += `${순회용현재노드.data}, `
      순회용현재노드 = 순회용현재노드.next;
    }
    return `[${s.slice(0, -2)}]`;
  }

    get fullData(){
      let 순회용현재노드 = this.head;
      순회용현재노드 = 순회용현재노드.next;
  
      let s ="";
      for (let i = 0; i < this.데이터수; i++){
        s += `${순회용현재노드.data}, `
        순회용현재노드 = 순회용현재노드.next;
      }
      return JSON.parse(`[${s.slice(0, -2)}]`);
    }

   inset(index, data) {
    let 순회용현재노드 = this.head;
    순회용현재노드 = 순회용현재노드.next;

    for (let i = 0; i < index - 1; i++){
      순회용현재노드 = 순회용현재노드.next;
    }

    let 새로운노드 = new Node(data);

    새로운노드.next = 순회용현재노드.next;
    순회용현재노드.next = 새로운노드;

    this.데이터수 += 1;
  }
   
}

a = new LinkedList();
a.append(1);
a.append(2);
a.append(3);
a.append(10);
a.append(30);
a.append(20);
console.log(a.length())
console.log(1)

📚 Reference

• 코딩문