Linked List in Date structure

Linked List

Node로 이루어져 있는 자료구조이다.

//노드 : 크기가 동적으로 변한다.

//노드 안에는 데이터를 담을 변수, 링크를 담을 변수를 가진다.

//연결리스트의 각 노드는 인덱스를 가지지 않는다.

데이터가 들어올때마다 동적으로 메모리를 할당하는 자료구조이다.

Dynamic Array(동적배열)이라고도 불린다.

크게 세가지의 종류가 있다.

//노드 안의 링크가 어떻게 구성되어있는지에 따라 다르다.

//Singly Linked List - 일방적이다.. 되돌아올 수 없다.

//Doubly Linked List  - 양방향

//Circular Linked List - 마지막 노드가 첫 번째 노드를 가리킨다.(계속 회전)

 

 

 

 

Linked List 그림예제_출처 : 코드스테이츠

연결리스트가 가지고 있는 method

addToTail(value) - 주어진 값을 연결 리스트의 끝에 추가한다.

remove(value) - 주어진 값을 찾아서 연결을 해제(삭제)합니다

getNodeAt(index) - 주어진 인덱스의 노드를 반환한다.

//값이 아닌 노드 반환한다.

//해당 인덱스에 노드가 없다면 undefined를 반환한다.

contains(value) - 연결리스트에 주어진 값을 가지는 노드의 존재 여부를 반환한다.

indexOf(value) - 주어진 값의 인덱스를 반환한다.

//없을 경우 -1을 반환한다.

 

코드로 구현해보기

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)
    //Node의 인스턴스 생성
    
    if(this.head === null){
      this.head = node;
      this.tail = node;
      this.size++
    //head가 없을 때,head와 tail에 노드 추가
    } else {
        this.tail.next = node;
        this.tail = node;
        this.size++;
      }//head가 있을 때, tail의 다음을 node로 하고 꼬리 추가
  }
  
  remove(value) {
    let currentNode = this.head
    let preNode = this.head
    
    if(this.head === value){
      this.head = this.head.next
    //value가 head일경우 head제거
    } 
      else {
        while(currentNode.value !== value){
          preNode = currentNode;
          currentNode = currentNode.next;
     //head를 유지하고 , head는 다음 head가 된다.
      }
    preNode.next = currentNode.next;
    }
  this.size--;
  }  
  
  getNodeAt(index) {
    let count = 0;
    let currentNode = this.head;
    
    while(count !== index){//count가 index 될 때까지
      count++; //count = count + 1
      currentNode = currentNode.next; // 다음노드를 계속 탐색
      if(!currentNode){
        return undefined;
      }
    }
    
    return currentNode;
  }// 왜 변수로 담아야하지 ?
  
  contains(value) {
    let currentNode = this.head;
  
    for(let i = 0; i < this.size; i++){ // size만큼 반복
      if(currentNode.value === value){
        return true; // value가 있다면 true
      } 
      currentNode = currentNode.next; // 다음노드를 계속 탐색
    } 
    return false; // value가 없다면 false
  }// 왜 변수로 담아야하지 ?
  
  indexOf(value) {
    let currentNode = this.head;
    let count = 0;
    
    while(currentNode.value !== value){ 
    //head의 value가 value와 같아질때까지
      count ++; // count = count + 1
      currentNode = currentNode.next; // 다음노드를 계속 탐색
      if(!currentNode){
        return -1; // 없다면 -1 return
      }
    }
    return count;  //있다면 count return
  }
  
  size() {
    return this.size;
  }//현재 size를 return
}

<-- 사용해보기 -->

let linkedList = new LinkedList;

linkedList;
//LinkedList {head: null, tail: null, size: 0}

linkedList.addToTail(1);
linkedList.addToTail(2);
linkedList.addToTail(3);
linkedList.addToTail(4);

linkedList;
//LinkedList {head: Node, tail: Node, size: 4}

linkedList.remove(3);

linkedList;
//LinkedList {head: Node, tail: Node, size: 3}

linkedList.getNodeAt(1);
//Node {value: 2, next: Node}

linkedList.getNodeAt(8);
//undefined

linkedList.contains(1);
//true

linkedList.contains(8);
/false

linkedList.indexOf(1);
//0

linkedList.indexOf(2);
//1

linkedList.indexOf(3);
//-1

linkedList.size
//3

 

연결리스트의 시간복잡도

추가하기 : O(1)

삭제하기 : O(1)

가져오기 : O(n)

//인덱스를 가지지 않기 때문에 전체 연결 리스트를 훑어야 한다.

 

링크드리스트를 이용한 예

파일 시스템(자료의 추가/삭제가 빈번히 일어날 경우)