10월 23일 TIL DataStructure : Linked List

feelslikemmmm·2020년 10월 26일
0

TIL

목록 보기
23/36
post-thumbnail

Data Structure

Linked List

연결 리스트는 그 크기가 동적인 자료구조로, 자료구조를 구성하는 요소, -우리는 이것을 노드(Node) 라고 부릅니다노드의 연결로 이루어진 자료 구조입니다. 연결 리스트의 어떠한 임의의 지점에 데이터의 추가와 삭제를 할 경우, O(1) (상수 시간)의 시간 복잡도를 갖습니다. 추가와 삭제에 대해 O(n) (선형 시간)의 복잡도를 갖는 배열과는 다르죠.

다만 이 추가와 삭제 속도에 대한 대가로, 연결 리스트의 각 노드는 인덱스를 갖지 않습니다. 그래서 어떤 특정 데이터를 연결 리스트에서 검색하고자 할 경우, 처음부터 전체 연결 리스트를 훓어야 하며, 이는 O(n) (선형 시간)의 복잡도를 필요로 합니다.

Linked List 구조

  • Linked list는 연결된 노드로 구성되어 있다.
  • 배열처럼 순서가 있고(ordered), 선형적(linear)인 자료 구조이다.
  • 각 노드를 살펴보면 data와 다음 노드의 주소를 담고 있다.여기서 다음 노드 주소를 참고하여 계속해서 노드가 연결되는 reference chain 형태이다.
  • 위의 그림에서 그린 것은 '단일 연결 리스트'이지만, 한 노드가 여러 노드와 연결되어 있는 '이중 연결 리스트' 또한 존재한다.
  • 보통 단일 연결 리스트는 자신의 다음 노드만 알고 자신의 전에 있는 노드는 알 수가 없다. 이중 연결 리스트는 이러한 문제를 풀고자 자신의 전에 위치한 데이터가 무엇인지 알고자 하여 생성되었고, 이 경우 단일 연결 리스트에 비해 메모리가 더 증가한다.
  • linked list는 stack, queue, hash table 등 다양한 자료구조를 구현하는데 사용된다.
  • 배열과 Linked List 비교
  • Search 기준: linked list는 매 요소마다 계속 chaining을 하면서 검색을 하기 때문에 메모리를 연속적으로 배치해 index 기준으로 바로 값을 검색하는 배열보다 성능상 좋지 않다. 그러나 메모리 할당은 적다.
  • 삽입/추가 기준: linked list는 중간에 데이터가 추가될 때 인덱스를 계속해서 변경해야 하는 배열에 비해 삽입/추가가 자유롭다.

Linked List method 구현하기

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 node = new Node(value); //new node 생성
    if(!this.head) {  //head가 비어있다면 첫번째 연결이기떄문에 head와 tail에 node 연결 
      this.head = node;
      this.tail = node;
      this._size++;
    } else { //head가 비어 있지 않다면 tail.next에 node 연결, tail에 node 연결, size++
      this.tail.next = node;
      this.tail = node;
      this._size++;
    }
    return node;
  }

  remove(value) {
    //주어진 값을 찾아서 연결을 해제(삭제)합니다
    if(!this.head) { //만약에 헤드가 없다면 undefined 리턴.
      return undefined;
    }

    if(this.head.value === value) { //만약에 헤드 value와 입력받은 value가 같다면
      this.head = this.head.next; // head는 head.next로 설정. (헤드 없애기)
      this._size--;
      return this; //현재 오브젝트 리턴.
    }
    
    let prevNode = this.head; //head를 prevNode로 설정. (0번째)
    let currentNode = this.head.next; //head.next를 currentNode 설정. (1번째)
    
    while(currentNode) { //currentNode 있을 때까지.
      if(currentNode.value === value) { //만약 currentNode.value가 value와 값이 같다?
        break; 
      }else { // 만약 값이 같지 않다?
        prevNode = currentNode;
        currentNode = currentNode.next; //한 칸씩 당겨 준다
        this._size--;
      }
    }
    prevNode.next = currentNode.next; //(currentNode.value 값이 같을 때)
    return this;
  }

  getNodeAt(index) {
    //주어진 인덱스의 노드를 찾아서 반환합니다. 값이 아니라 노드를 반환해야 하는 것에 주의하세요. 해당 인덱스에 노드가 없다면 undefined를 반환합니다.
    let currentNode = this.head;
    if(index > this._size) { //입력받은 index가 size보다 크면 undefined에 저장
      return undefined;
    } else { //index가 size보다 작으면 for문을 돌리는데, i<index로 설정하고 1번의 변수를 1번의 변수.next로 설정해서 index까지 도달.
      for(let i = 0; i < index; i++) {
      currentNode = currentNode.next;
      }
    }
    return currentNode; //해당 인덱스 리턴
  }

  contains(value) {
    //연결리스트에 주어진 값을 가지는 노드의 존재 여부를 반환합니다.
    let currentNode = this.head;
      while (currentNode) { //this.head가 있을때까지
        if( currentNode.value === value) { //입력받은 value와 currentNode.value가 같다면 리턴 true.
          return true;
        } else { // 같지 않다면 currentNode = currentNode.next
          currentNode = currentNode.next; 
        }
        }
    return false; //다 돌았음에도 불구하고 없다면 false 리턴
  }

  indexOf(value) {
    //주어진 값의 인덱스를 반환합니다. 없을 경우 -1을 반환합니다.
    let currentNode = this.head; //head변수
    let count = 0; //index로 사용할 count변수
    while (currentNode) { //currentNode가 있을때까지
      if(currentNode.value === value) { //해당 인덱스와 currentNode.value가 같다면 인덱스 변수 리턴.
        return count;
      } else {
        count++; //아니라면 index 변수++, currentNode = currentNode.next
        currentNode = currentNode.next;
      }
    }
    return -1; //다 돌았음에도 불구하고 없다면 -1 리턴.
  }

  size() {
    return this._size;
  }
}

module.exports = LinkedList;
profile
꾸준함을 잃지 말자는 모토를 가지고 개발하고 있습니다 :)

0개의 댓글