[자료구조] 연결 리스트

연결 리스트란?

데이터안에 각 노드들이 있고 각 노드마다 데이터와 포인터가 존재하는 자료구조이다.

각 노드의 포인터가 다음 노드의 주소를 가리키고 있다. 그리고 각 노드는 메모리상에 연속적인 주소에 할당이 되는게 아닌 개별적으로 남는 공간에 할당이 된다.
배열의 경우에는 일정한 크기의 메모리가 연속적으로 할당이 되어서 선언이 되는데 연결 리스트는 필요할 때 메모리상에 남는 공간에 데이터가 할당되기 때문에 메모리 누수 문제를 해결할 수 있다.

1. 삽입

연결리스트 중간이나 끝이나 시작점등 어느 위치에서 삽입해도 시간복잡도는 O(1)이 소요가 된다.
원하는 데이터 노드를 메모리상에 선언하고 기존 노드에서 포인터에 새로운 노드를 연결시켜주기만 하기 때문에 이와 같이 효율적으로 원하는 공간에 데이터를 삽입하는게 가능하다.

2. 삭제

삭제도 마찬가지로 포인터를 끊어주기만 하면 되기때문에 O(1)의 시간복잡도만 있으면 충분히 삭제할 수 있다.

3. 순회

순회는 무조건 처음 노드부터 순서대로 순회해서 원하는 값을 찾아야 한다.
여기서 연결 리스트에 단점이 있는데 배열은 원하는 데이터의 경우에는 인덱스값으로 O(1)의 시간복잡도로 참조가 가능하지만 연결 리스트의 경우에는 인덱스로 접근하는게 불가능하다.
모든 참조는 Head부터 시작해 원하는 데이터가 나올때까지 순회를 해야한다는 단점이 존재한다.

연결 리스트 구현

// 연결리스트에 존재하는 각 node를 선언
class Node {
  constructor(data, next = null) {
    this.data = data;
    this.next = next;
  }
}

// 연결리스트 class
class LinkedList {
  constructor() {
    this.head = null;
    this.size = 0;
  }
  
  // 연결리스트에 아무 원소도 없을때 처음 노드를 추가하는 메서드
  insertFirst(data) {
    this.head = new Node(data, this.head);
    this.size++;
  }
  
  // 연결리스트 마지막에 새로운 노드를 추가하는 메서드
  insertLast(data) {
    let node = new Node(data);
    let current;
    
    if (!this.head) {
      this.head = node;
    } else {
      current = this.head;
      
      while (current.next) {
        current = current.next;
      }
      
      current.next = node;
    }
    this.size++;
  }
  
  // 연결리스트 중간에 새로운 노드를 추가하는 메서드
  insertAt(data, index) {
  	if (index > 0 && index > this.size) {
      return;
    }
    
    if (index === 0) {
      this.head = new Node(data, this.head);
      this.size++;
      return;
    }
    
    const node = new Node(data);
    let current;
    let previout;
    
    current = this.head;
    let count = 0;
    
    while (count < index) {
      previous = current;
      count++;
      current = current.next;
    }
    
    node.next = current;
    previos.next = node;
    
    this.size++;
  }
  
  // 연결 리스트에서 값을 참조하는 메서드
  getAt(index) {
  	let current = this.head;
    let count = 0;
  	
    while (current) {
      if (count !== index) {
      	count++;
        current = current.next;
      } else {
      	return current.data;
      }
    }
    return null;
  }
  
  // 연결 리스트에서 노드를 삭제하는 메서드
  removeAt(index) {
  	if (index > this.size) {
      return;
    }
    
    let current = this.head;
    let previous;
    let count = 0;
    
    if (index === 0) {
      this.head = current.next;
    } else {
      while (count < index) {
      	count++;
        previous = current;
        current = current.next;
      }
      
      previous.next = current.next;
    }
    
    this.size--;
  }
}

출처

https://code-lab1.tistory.com/2