연결리스트와 이중연결리스트(LinkedList Family)

연결 리스트(Linked List)

이름 그대로 연결 리스트이다. 각 데이터들을 줄로 매듭을 지어 묶어놓은 것처럼 데이터들 끼리 이어져 있다는 추상적인 이유로 연결 리스트라고 부른다. 이 데이터들은 동적이며, 이어주는 줄을 링크라고 부른다. 맨 앞의 노드를 의미하는 head와 맨 마지막노드는 tail이라는 구조로 이어져있다.

노드의 구조

연결리스트의 각 노드(node)는 두개의 필드가 존재한다.

• 값을 저장해줄 데이터 필드 : data 나 value등으로 불린다.
• 다음 노드의 주소를 담고있는 포인터 : next나 next link, pointer라고 불린다.

이런 연결리스트 구조는 쭉 나열되어 있는 배열의 구조와 다르게 다양한 공간에 흩어져있는 데이터들을 포인터로 이어주기만 하 면 된다. 처음 노드는 head라고 하고, 가장 마지막 노드는 tail이라고 한다. 각 노드들은 본인의 다음 노드를 기억한다. tail의 뒤에 새로은 노드가 묶이지 않는다면 Pointer는 빈 공간 null을 가르킨다.

LinkedList 와 Array List의 차이점

Array List(배열리스트) : 탐색과 정렬이 잦으면 유리

가장 간단한 메모리 데이터 구조이다.

• 동일한 데이터 타입을 연속적으로 저장 가능
• 간단하고, 사용이 쉬우며 데이터를 참조하기 쉽다.
• 자바스크립트가 아닌 일반적인 배열에서는 고정된 크기를 가지고 있어 중간에 위치한 요소를 넣고 빼려면, 반복 연산이 잦아진다.

Linked List(연결리스트) : 추가와 삭제가 많은 작업시 유리

배열처럼 차례대로 저장하지만, 메모리상에 연속적으로 위치하지 않는다. 노드로 구현된 리스트이고, 링크 당 4 byte의 메모리를 차지하고, 더블 링크드 일경우 8 byte의 링크 메모리를 차지한다.

• 배열에 비해 데이터 추가 및 삽입이 용이
• 배열보다 메모리를 효율적으로 사용가능
• 특정 위치의 데이터를 검색하기 위해서는 처음부터 끝까지 순회해야한다. 너무 비효율적

LinkedList의 활용

포토샵이나, 문서작업 툴에서 실수 할경우 Ctrl + Z, Ctrl + Y로 지워진 내용 복원이나 복원 취소를 할 수 있고,

이미지 뷰어에서 이전이미지 다음 이미지를 찾는다던가, 음악 플레이어의 재생목록 변경 등 이있다.

Linked List 3가지 종류

Singly Linked List

null : 어떠한 데이터가 들어있지 않는 공간

.head : 리스트의 첫버째 노드(node)

.tail : 리스트의 마지막 노드(node)

.next : 다음 노드의 주소를 가지고 있다. tail의 pointer는 null

연결리스트 기본 메소드

.addToTail(value) : 리스트의 마지막에 추가한다.(.append()와 같음)

.prepend(value) : 리스트의 처음에 추가한다.

.remove(value) : data, value를 삭제한다.

.getNodeAt(index) : data의 인덱스를 가져온다.

.contain(value) : 데이터가 리스트에 존재하는지 Boolean값으로 확인한다.

.size() : 연결 리스트가 가진 총 데이터 개수를 반환한다.

JavaScript Linked List

• 단일 연결리스트 생성함수

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

  toString(cb) {
   return cb ? cb(this.value) : `${this.value}`; 
  }
}

export default class LinkedList {
  constructor(compares){
    this.head = null;
    this.tail = null
    this.compare === compares
  } 
}

• 삽입

prepend

prepend(value) {
  //헤드로 노드 추가
  const newNode = new LinkedListNode(value, this.head);
  this.head = newNode;

  //만약 꼬리가 없으면 새 노드를 꼬리로 만든다
  if(!this.tail) {
   this.tail = newNode;
  }

  return this;
}

append

append(value) {
  const newNode = new LinkedListNode(value);

  //만약 헤드가 아직 없다면 새노드의 헤드와 꼬리를 만든다.
  if(!this.head) {
    this.head = newNode;
    this.tail = newNode;

    return this;
  }
}

• 삭제

delete

delete(value){
 if(!this.head){
   return null;
 } 

  let deleteNode = null;
  let equelNode = (a, b) =>{
   return this.compares(a, b) === 0 
  }

  //헤드를 삭제하는 경우 다른 노드를 다음 노드로 만든다.
  //헤드는 새로운 헤드가 생성된다.
  while(this.head && equelNode(this.head.value, value)) {
    deleteNode = this.head;
    this.head = this.head.next;
  }

  let currentNode = this.head;

  if(currentNode !== null){

    //다음 노드를 삭제해야 하는 경우
    //그 다음의 노드를 앞으로 당겨와 이어지는 노드로 만든다.

    while(currentNode.next){
    if(equelNode(currentNode.next.value, value)){
     deleteNode = currentNode.next;
     currentNode.next = currentNode.next.next;
    } else {
     currentNode = currentNode.next;
    }
   }
  }
  return deleteNode;  
}

Delete head

deleteHead() {
  if(!this.head) {
    return null 
  }

  const deleteHead = this.head;

  if(this.head.next) {
   this.head = this.head.next;
  }else {
   this.head = null;
   this.tail = null;
  }
  return deleteHead;
}

Delete Tail

deleteTail() {
  const deletedTail = this.tail;

  if(this.head === this.tail) {
    this.head = null;
    this.tail = null;

    return detetedTail;
  }

  let currentNode = this.head;
  while(currentNode.next) {
    if(!currendNode.next.next){
     currentNode.next = null;
    } else {
     currentNode = currentNode.next; 
    }
  }
  this.tail = currentNode;

  return deletedTail;
}

• 탐색

find

find({value = undefined, callback = undefined}) {
  if(!this.head) {
    return null; 
  }

  let currentNode = this.head;
  let equelNode = (a, b) =>{
   return this.compares(a, b) === 0 
  }


  while(currentNode) {

   //콜백함수로 지정되면 콜백함수로 노드를 찾는다.
   if(callback && callback(currentNode.value)){
     return currentNode;
   }


   //값이 지정된 경우 값으로 비교 한다.
   if(value !== undefined && equelNode(currentNode.value, value)) {
    return currentNode; 
    }

    currentNode = currentNode.next
  }
  return null;
}

reserve

reserve() {
  let currentNode = this.head;
    let prevNode = null;
    let nextNode = null;

    while (currentNode) {
      // 현재 노드를 순회하여 다음 노드를 저장한다.
      nextNode = currNode.next;

      // 현재 노드의 다음에 위치한 노드를 이전노드에 연결한다.
      currentNode.next = prevNode;

      // 이전 노드와 현재 노드는 한 단계 앞으로 이동하고 새 노드를 붙인다.
      prevNode = currentNode;
      currentNode = nextNode;
    }

    // 머리와 꼬리를 재설정한다.
    this.tail = this.head;
    this.head = prevNode;

    return this;

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

일반적으로 말하는 연결리스트는 단일 연결리스트로 일방적인 방향으로 연결되어있지만, 이중 연결리스트는 노드가 서로 양 방향으로 연결되어있다. 아래 그림처럼 이전 노드(Previous)와 다음 노드(next)로 구성되어있다.

이중 연결리스트의 장점

이런 양방향 탐색의 가장 큰 장점은 특정 인덱스 위치의 요소를 가져올 때 단반향 연결리스트보다 훨씬 수월하다.

위 그림에서와 같이 6개에 노드가 존재했을때 단일 연결리스트는 처음부터 시작하여 next를 이용해 탐색하고, 4번째 이후의 엘리먼트는 previous를 이용해서 조회한다. 만약 상당한 수의 노드가 존재한다면 처음부터 끝까지 탐색해야 하기 때문에 상당히 비효율적이다. 양방향 리스트는 탐색하는 엘리먼트가 반으로 줄어든다.

이중 연결리스트는 next뿐만 아니라 previous를 이용하 탐색이 가능하다. 따라서 상황에 따라 탐색의 방향이 바뀌어야 하는 경우 이중 연결리스트를 사용한다.

이중 연결리스트의 단점

이중연결리스트는 이전 노드를 지정해줘야 하므로 변수를 추가해줘야한다. 그렇기 때문에 메모리를 더 많이 사용한다는 의미를 가지고, 구현 또한 복잡하다는 단점이 존재한다. 하지만 장점이 크기 떄문에 이중 연결리스트를 많이 사용한다고 들었다.

기본 연결리스트 기본 메소드

.add(value) : 리스트 어느 곳에서나 위치를 추가한다.

.remove(value): 리스트 양 끝이나 사이의 노드를 삭제한다.

.reverseTraversal : 리스트를 역순으로 순회한다.

JavaScript Doubly Linked List

• 노드 생성함수

class DoublyLinkedListNode {
 constructor(value, next = null, previous = null) {
   this.value = value;
   this.next = next;
   this.previous = previous;
 }

  toString(cb) {
    return cb ? cb(this.value) : `${this.value}`;
  }
}

class DoublyLinkedList {
  constructor(compares) {

    this.head = null;
    this.tail = null;

    this.compare = compares
  }

• 삽입

  prepend

  prepend(value) {
  const newNode = new DoublyLinkedListNode(value, this.head);
  
  if(this.head) {
  this.head.previous = newNode; 
  }
  
  this.head = newNode;
  
  if(!this.tail) {
    this.tail = newNode; 
  }
  
  return this;
  }

  append

  append(value) {
  const newNode = new DoublyLinkedListNode(value);
  
  if(!this.head){
   this.head = newNode;
   this.tail = newNode;
  
   return this;
  }
  
  this.tail.next = newNode;
  
  newNode.previous = this.tail;
  
  this.tail = newNode;
  
  return this;
  }

• 삭제

prepend

delete(value) {
 if(!this.head){
   return null; 
 }

 let deleteNode = null;
 let currentNode = this.head;
 let equelNode = (a, b) =>{
   return this.compares(a, b) === 0 
  }

  while(currentNode) {
   if(equelNode(currentNode.value, value)) {
     deleteNode = currentNode; 

     if(deleteNode === this.head) {

       this.head = deleteNode.next;

       if(this.head) {
        this.head.previous = null; 
       }

       if(deleteNode === this.tail) {
        this.tail = null 
       }

     } else if (deleteNode === this.tail) {
       this.tail = deleteNode.previous;
       this.tail.next = null;
     } else {
       const previousNode = deleteNode.previous;
       const nextNodee = deleteNode.next;

       previousNode.next = nextNode;
       nextNode.previous = previousNode;
     }
   }
    currentNode = currentNode.next;
  }
  return deleteNode;
}

prepend

prepend

해시 테이블(Hash Table)

헤시 테이블은 key, value로 데이터를 저장하는 자료구조로, 빠르게 데이터를 검색할 수 있는 장점을 가진다. 해시 테이블은 각각 Key값에 해시함수(hash function)를 통하여 배열의 Index를 생성하고, 이 index를 bucket(배열)안에 저장한다. 이러한 과정을 해싱(hashing)이라고 하며, 고유한 주소값으로 key와 value로 검색해서 데이터를 바로 찾을 수 있다는 큰 장점을 가지고 있다.

hash table :

hash function :

bucket :

tuple :

key :

장점

적은 리소스로 많은 데이터를 효율적으로 관리한다.

index에 해시

충돌

충돌상황 해결방법

1. Open Addressing

2. Close Addreassing

실생활 사용

ref:망규블로그,비쥬얼고 넷,
암호코드 미디엄,
ratsgo 깃헙
라이스인더라면 벨로그,오픈튜토리얼