Linked List

• 연결 리스트는 크기가 동적인 자료구조다.
• 각 데이터들을 포인터로 연결하여 관리하는 자료구조.
• '노드'라는 객체로 이루어져 있다.

노드 이미지	노드의 구성
	1. 데이터 영역 : 데이터를 저장 2. 포인터 영역 : 다음 데이터가 저장된 노드를 가리키는 포인터 영역 (3. 전 노드를 가리키는 포인터 영역 : 이중 연결 리스트 일 때)

자바스크립트에서 연결 리스트 형태(?):

const list = {
    head: {
        value: 1
        next: {
            value: 2   
            next: {
                value: 3
                next: {
                    value: 4
                    next: null	
                    }
                }
            }
        }
    }
};

참조 : How to Implement a Linked List in JavaScript

연결리스트 종류

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

• 앞으로만 아이템(노드)을 순회 할 수 있다.

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

• 앞, 뒤로 아이템(노드) 순회.
• 노드에 prev pointer(전 노드를 가리킨다) 추가

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

• 마지막 노드 포인터에 첫번째 노드(head node(?))를 연결한다.

실제 사례

• Music Player
• Image viewer
• Previous and next page in web browser
• conga line / 강강술래

배열과 연결리스트의 차이점

	배열	연결리스트
장점	- 랜덤 엑세스가 빠르다 (즉, 매우 빠르게 접근 가능) (O(1))	- 동적으로 메모리 사용가능 - 메모리 호율적 사용 - 데이터 재구성 용이 (O(1)) - 대용량 데이터 처리 적합
단점	- 메모리 사용 비효율적 - 배열 내의 데이터 이동 및 재구성이 어렵다(O(n))	- 특정 위치 데이터 검색할때 느리다(O(n)) - 메모리를 추가적으로 사용해야한다

참조 | 자료구조 : 연결리스트 (Linked list)

Property

• head : 첫 노드를 가리킨다
• tail : 마지막 노드를 가리킨다
• _size : 노드의 갯수

Method

• addToTail(value) : value를 연결리스트 끝에 추가
• remove(value) : value를 찾아서 연결 해제(삭제)
• getNodeAt(index) : index의 노드를 찾아서 반환.
  (값이 아니라 노드를 반환해야 된다.) 해당 index의 노드가 없다면 undefined 반환
• contains(value) : 연결리스트에 value를 가지는 노드의 존재 여부 반환
• indexOf(value) : value의 인덱스를 반환. 없을 경우 -1 반환

Additional Method

• insert(newElement, item) : item 을 요소로 갖는 node 뒤에 newElement 를 요소로 갖는 node를 추가
• isEmpty() : 데이터가 하나도 없다면 true를, 그 외엔 false를 반환

  참조 :

  • 자바스크립트 자료구조 연결 리스트(Linked List)
  • [자바스크립트] LinkedList 연결 리스트 클래스

Pseudocode

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

class LinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
    this._size = 0;
  }

  addToTail(value) {
    // 연결리스트에 추가하기 위해 새로 생긴 노드를 할당할 변수 선언
      // let newNode = new Node(value);
    // this.head가 null일때 head와 tail에 newNode할당
    // 그 외에는 tail.next에 newNode를 할당하고 tail을 newNode로 재할당하며 계속 이어 붙여 준다.
    // this._size++;

  remove(value) {
// 방법 1.
    // prevNode와 currNode 변수 선언
    // this.head가 있을때
     // this.head.value와 value가 같을 때 this.head에 this.head.next 재할당
     // this._size--;
     // 그 외에
       // for문으로 (i는 0부터 this.size()까지 하나씩 늘어난다)
         // currNode는 prevNode.next로 재할당(포문돌때마다 재할당된다)
         // 만약 currNode.value가 주어진 value와 같을때
           // prevNode.next = currNode.next 재할당
           // this.size--;
         // for문 나가기 전에 prevNode에 currNode 재할당
// 방법 2. getNodeAt()과 indexOf()메소드를 먼저 생성
    // this.indexOf(value)를 통해 얻은 값을 index변수에 할당
    // 만약 인덱스가 0이라면 (head가 걸렸을때)
      // this.head = this.head.next
    // index > 0이면
      // currNode에 this.getNodeAt(index)를 할당
      // prevNode에 this.getNodeAt(index - 1)할당
      // prevNode.next = currNode.next;
  }

  getNodeAt(index) {
    // 반환할 변수 currNode 선언(this.head부터 시작해야되닌깐 this.head로 할당)
    // for문 (i는 영부터 this.size()까지 하나씩 더한다)
      // 만약 i가 주어진 index값과 같을때 currNode 리턴
      // currNode = currNode.next로 재할당
  }

  contains(value) {
    // return Boolean(this.indexOf(value) !== -1);
  }

  indexOf(value) {
    // currNode에 this.head 할당
    // idx는 0할당
    // while문으로 currNode가 null이 아닐때까지 도는 조건식 적어준다
      // 만약 currNode.value가 value랑 같을때 idx리턴
      // currNode = currNode.next로 재할당
      // idx++
    // 노드 한개씩 검사해서 안나오면 -1 반환
  }

  size() {
    // return this._size;
  }
}