Linked-list

i do as i say·2020년 5월 4일
CODESTATESTILimmersive
1


잡숴 보세요 아주 유익하고 맛있습니다
여기에 어떤 분이 "프로그래밍 튜토리얼 파트 제로" 이런 댓글 달아 놓으셨던데 진짜 울고 싶었읍니다.

이건.. 그냥.. 제 검색어가 너무 너무라서 올려 봅니다..ㅋㅋㅋㅋㅋ

안녕하세요? 주말에 공부 안 했다가 발등에 불똥이 떨어져 버린 사람입니다. 잔말 없이 빨리 시작해 보겠습니당나귀. 바빠서 비유 같은 걸 생각하지를 못했네요. 흑흑. 내일은 꼭 시간이 많길 바랍니다.

요번부터는 목차가 생깁니다. 왜냐구요. 정리할 게 많기 때문입니다. 쓰다가 헷갈리지 않게 써 봅니다.

연결 리스트(linked list)란?
배열 리스트와 연결 리스트의 장단점
연결 리스트의 특징
연결 리스트의 종류
실생활과 닿아 있는 연결 리스트?
연결 리스트의 method
수도 코드
코드 구현

연결 리스트(linked-list)란?

이름... 그대로입니다. 링크 목록이라는 뜻인데요.(...) 각 데이터들을 한 줄로 연결시킨 모양을 띄우고 있는 자료 구조입니다. 여기서 왜 링크라는 게 나오냐면, 그 데이터들을 링크로 연결을 시키기 때문입니다. 네.

연결 리스트의 구조를 그림으로 한번 볼까요?

(한방향 리스트)
오늘은 좀 잘 그린 것 같네요. ㅎㅎ 보통 노드를 그릴 때 일자형으로 그리더라구요. 그런데 저는 이게 조금 더 이해가 가서 이렇게 그려 보았습니다. 그림을 차근차근 정리해 봅시다.

연결 리스트에서 데이터와 링크를 가지고 있는 박스를(크기가 동적인 자료구조로, 자료구조를 구성하는 요소)노드라고 합니다. 노드는 데이터만 가지고 있을 수도, 링크만 가지고 있을 수도 없는, 걍 (원소 자신인)데이터와 링크 한 세트라고 보시면 됩니다. 보시는 것과 같이 노드의 링크는 그 다음 데이터를 가리키고 있는데요, 링크를 통해서 데이터를 추가하고, 삭제하며 탐색도 가능합니다. 같이 있는 게 아닙니다! 데이터를 저장할 장소와 다음 원소를 가리키기 위한 장소가 구분되어 있습니다.

배열과 유사하죠? 그래서 배열과 비교를 많이 하는데요,

배열 리스트와 연결 리스트의 장단점

배열은 arr = [1, 2, 3, 4] 형태로 가지고 있는 거 아시죠? 요 배열 리스트와 연결 리스트는 아주 유사하지만, 링크라는 것으로 아주 크게 차이가 나는데요.

배열 리스트
가장 간단한 메모리 데이터 구조이다.
(장) 동일한 데이터 타입을 연속적으로 저장할 수 있다.
(장) 간단하고, 사용이 쉬우며 데이터를 참조하기 쉽다.
(단) 고정된 크기(JS 제외)를 가지고 있어서 배열의 처음이나 중간에서 원소를 넣고 빼려면 비싼 연산을 빈번하게 해야 한다.

연결 리스트
일련의 원소를 배열처럼 차례대로 저장하지만 원소들이 메모리상에 연속적으로 위치하지 않는다. 노드로 구현된 리스트이다. 링크 하나에 4 byte 메모리를 차지하며, 더블 링크드일 경우엔 노드 하나에 8 byte의 링크 메모리를 차지한다.
(장) 배열에 비해 데이터의 추가 및 삽입이 용이하다.
(장) 배열보다 메모리를 효율적으로 쓸 수 있다.
(단) 특정 위치의 데이터를 검색하기 위해서는 처음부터 끝까지 순회해야 하기 때문에 탐색에 비효율적임.

탐색과 정렬을 자주 한다면 배열 리스트
추가와 삭제가 많다면 연결 리스트

연결 리스트의 특징

위에서 다 설명한 것 같지만... 다시 한 번만 적어 봅니다.

  1. 연속되는 항목들이 포인트로 연결되어 있음.
  2. 마지막 항목은 Null을 가리키고 있음. (마지막이라 연결한 노드가 없기 때문)
  3. 프로그램이 수행되는 동안 크기가 동적으로 커지거나 작아짐.
  4. 메모리 공간 낭비가 적지만 포인터 메모리가 필요함.
  5. 배열에 비해 데이터의 추가와 삽입에 용이.
  6. 단방향(양방향이라도) 순차적으로 탐색하지 않으면 요소에 접근이 불가하기 때문에 탐색 속도가 떨어짐.
  7. 데이터를 추가하는 건 객체 할당임.
  8. 링크를 끊어 버리면 데이터가 삭제되기 때문에 (JS기준) 만약 head에서 노드를 전체 삭제하고 싶다면 head에 있는 링크를 끊어 버리기만 하면 된다.

그리고 이건 제가 구현을 하면서 느낀 건데, 연결 리스트의 그림과 구현 코드가 살짝(그런데 체감으로는 아주 많이임) 달랐습니다. 일단 헤드에 연결을 전부 해 놓구요, 테일에는 제일 마지막 데이터만 걸어 주었습니다.

요런 닉김이었어요. 이거 보니까 진짜 동물이 떠오르긴 하네요.

그림 안 그리려고 했는데..(ㅠㅠ)
아무튼 이렇게, 달려 있긴 하지만 꼬리가 몸통은 아니잖아요? 이런 느낌이긴 한데, 역시 개발자는 코드죠. 코드로 확인하면 제가 말한 느낌이 팍 옵니다.

head: {0: 'apple', next: {1: 'banana', next: {2: 'dream', next: null}}}}
tail: {2: 'dream', next: null}

어떤 모습인지 아시겠나요? 뜨흐흑.
조금 더 자세한 그림이 담긴 유익 블로그도 추가합니다.
https://medium.com/@lyhlg0201/immersive-sprint-js-linkedlist-4edcb5928a9e


요 그림은 데이터를 삭제할 때의 모습인데요, data2를 삭제해 주는 것이 아닌, data 1의 링크를 2가 아닌 3으로 다시 연결해 주면 data 2는 head에서 자동으로 탈락되어 사라지게 됩니다. 추가도 마찬가지겠지요? data1의 링크를 3이 아닌 넣으려고 하는 데이터에 연결해 주고, 넣으려고 하는 데이터의 포인터를 3으로 연결해 주면 됩니다.

연결 리스트의 종류

* 모든 리스트의 코드를 구현하지는 않습니다!

Singly linked list (일방향 연결 리스트)

지금까지 말했던 게 바로 일방향 연결 리스트입니다. 일방향 연결 리스트는 노드에 포인터(다음 노드를 가리키는 링크)가 한 개인 연결 리스트인데요, 이 리스트의 장점은 노드당 포인터 데이터를 4 바이트만 차지해서 이중 연결 리스트보다 데이터를 아낄 수 있다는 점입니다. 다만 일방향이기 때문에 현재 노드는 이전 노드로 돌아가는 법을 모릅니다. 오직 직진만이 있을 뿐.

Doubly linked list (이중 연결 리스트)

노드에 포인터가 두 개 있는 이중 연결 리스트인데요, 일방향 연결 리스트와 똑같지만 앞서 말한 것처럼 노드에 포인터가 두 개 있다는 점이 다른데요, 이 두 개의 포인터는 전과 후를 가리키고 있기 때문에 일방향과는 달리 이전으로 갈 수도, 이후로도 갈 수도 있습니다. 포인터가 두 개가 생겼으니 데이터도 두 배로 먹겠죠. 8 바이트를 차지합니다.

Circular linked list (환형 연결 리스트)

연결 리스트에 있는 헤드와 테일이 붙여져 있어, 원의 모양과 같다고 하여 환형 리스트인데요. 테일의 포인터가 null을 가리키고 있는 것이 아닌 head를 가리키고 있는 것입니다. 노드 6 번에 있다가 4 번으로 가야 된다면, 일방향 리스트는 다시 시작해야 되지만 환형 리스트는 7, 8, 9, 10을 지나 다시 0, 1, 2, 3, 4로 갈 수 있겠죠? 순회할 때 좋은 연결 리스트입니다.

실생활과 닿아 있는 연결 리스트?

실생활과 닿아 있기 전, 연결 리스트와 유사한 비유가 하나 떠올랐어요. 지하철역입니다.


일방향으로 가고, 역에 도착할 때마다 다음 역을 말해 주는 게 연결 리스트와 닮아 있습니다. 음, 또, 2호선 같은 경우엔 환형으로 되어 있는 연결 리스트네요. 그냥 갑자기 떠올라서 말씀을 드렸습니다. 하핫. 런닝맨도 있겠네요. 뭐 하나 찾으면 어디 가라고 지시 써 있고, 뭐 하나 찾으면 어디 가라고 지시 써 있고.

우리가 사용하고 있는 것에 연결 리스트가 숨어 있습니다.
멜론 등 음악을 듣는 플랫폼을 사용할 때, 다음 곡이나 이전 곡으로 갈 수 있는 것들에도 연결 리스트를 사용하고, 포토샵처럼 ctrl+z로 했던 것을 지우거나 ctrl+y로 다시 나타내는 것을 할 수도 있겠구요, 이미지 뷰어처럼 다음 이미지, 이전 이미지를 볼 수 있게할 수도 있겠습니다.

연결 리스트의 method

* 어디서든 추가와 삭제가 가능하지만 끝에만 추가하는 것으로 구현해 봅니다.

  • addToTail(value): 연결 리스트의 마지막에 데이터를 추가합니다.

  • getNodeAt(index): 인덱스를 넣었을 때, 그 인덱스가 어떠한 값을 가지고 있는지 반환합니다.

  • contains(value): 해당 값이 연결 리스트에 있는지 true와 false로 반환합니다.

  • indexOf(value): 해당 값이 어떤 인덱스에 있는지, 인덱스 값과 -1로 반환합니다.

  • remove(value): 해당하는 연결 리스트의 값을 지웁니다.

  • size(): 연결 리스트의 사이즈를 반환합니다.

수도 코드 작성

실제 코드로 구현하기에 앞서 수도 코드로 작성해 보겠습니다.
Node의 생성자 함수를 따로 구현했습니다.
Linked-list의 구현 함수에는 constructor로 head와 tail, size가 있습니다.

  • addToTail(value)
  1. head와 tail에 참조 연결
    0-1. new를 이용해 node 생성 (let curNode = new Node())
  2. 만약 head가 비어 있다면? 첫 연결이기 때문에 head와 tail에 node 참조 연결을 해 준다.
  3. 만약 head가 비어 있지 않다면?
    2-1. tail.next에 node 연결
    2-2. tail에 node 연결
  • getNodeAt(index)
  1. 헤드를 변수에 저장한다.
  2. 만약, index가 size보다 크다면?
    2-1. undefined에 저장한다.
  3. 만약, Index가 size보다 작다면?
    3-1. for문을 돌리는데, i<index로 설정.
    3-2. 1번의 변수를 1번의 변수.next로 설정해서 index까지 도달.
    3-3. 그 index를 리턴.
  • contains(value)
  1. 헤드를 curNode 변수에 저장한다.
  2. while문을 설정함. curNode가 있을 때까지.
  3. 해당 인덱스와 curNode.value가 같다면 리턴 true.
    3-1. 같지 않다면 curNode = curNode.next
  4. 다 돌았음에도 불구하고 없다면 false 리턴.
  • indexOf(value) (상단의 콘테인 함수와 비슷)
  1. 헤드를 curNode 변수에 저장한다.
  2. indexCount 변수를 설정.
  3. while문을 설정함. curNode가 있을 때까지.
  4. 해당 인덱스와 curNode.value가 같다면 인덱스 변수 리턴.
  5. 아니라면 인덱스 변수++, curNode = curNode.next
  6. 다 돌았음에도 불구하고 없다면 -1 리턴.
  • remove(value): 해당하는 연결 리스트의 값을 지웁니다.
  1. 만약에 헤드가 없다면 undefined 리턴.
    0-1. 만약에 헤드 value와 value가 같다?
    0-2. head는 head.next로 설정. (헤드 없애기)
    0-3. 현재 오브젝트 리턴.
  2. head를 prevNode로 설정. (그러니까 0번째)
  3. head.next를 curNode로 설정. (그러니까 1번째)
  4. while문을 설정함. curNode가 있을 때까지.
  5. 만약 curNode.value가 value와 값이 같다?
    4-1. break;
  6. 만약 값이 같지 않다?
    5-1. prevNode = curNode
    5-2. curNode = curNode.next (한 칸씩 당겨 줌)
  7. (curNode.value 값이 같을 때) prevNode.next = curNode.next
  8. size--
  9. 오브젝 리턴
  • size()
  1. size를 리턴한다.

JS 코드

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

class LinkedList {
  constructor() {
    this.head = head;
    this.tail = tail;
    this._size = 0;
  }
  
  addToTail(value) {
    let newNode = Node();
    if(!this.head) {
      this.head = newNode;
      this.tail = newNode;
    } else{
      this.tail.next = newNode;
      this.tail = newNode;
    }
    this._size++;
    return this;
  }
    
  getNodeAt(index) {
    let curNode = this.head;
    if(index > this._size) return undefined;
    for(let i = 0; i < index; i++) {
      curNode = curNode.next;
    }
    return curNode;
  }
  
  contains(value) {
    let curNode = this.head;
    while(curNode) {
      if(curNode.value === value) {
        return true;
      }else {
        curNode = curNode.next;
      }
    }
    return false;
  }
  
  indexOf(value) {
    let curNode = this.head;
    let indexCount = 0;
    
    while(curNode) {
      if(curNode.value === value) {
        return indexCount;
      }else{
        indexCount++;
        curNode = curNode.next;
      }
    }
    return -1;
  }
    
  remove(value) {
    if(!this.head) return undefined;
    if(this.head.value === value) {
      this.head = this.head.next;
      return this;
    }
    
    let prevNode = this.head;
    let curNode = this.head.next;
    
    while(curNode) {
      if(curNode.value === value) {
        break;
      }else {
        prevNode = curNode;
        curNode = curNode.next;
      }
    }
    prevNode.next = curNode.next;
    this._size--;
    return this;
  }
      
  
  size() {
    return this._size;
  }

JS 코드 다시 쓰는 거 정말 힘들고 공부 많이 된다 흑흑

profile
i do as i say
커신이 고칼로리
이전 포스트

5월 1주차 주말 회고

다음 포스트

linked-list와 hash Table 오답 노트

1개의 댓글