연결 리스트

• 동적인 자료 구조: 필요할 때마다 원소를 추가/삭제할 수 있고 크기가 계속 변함
• 원소를 차례대로 저장하긴 하지만, 원소들이 메모리상에 연속적으로 위치하지는 않음.
• 원소는 배열과 달리 원소를 추가 삭제할 때 다른 원소를 이동(비싼 연산)시킬 필요는 없지만 원소를 찾을 때까지 처음부터 루프를 반복해야 함.

구현

function LinkedList() {
  
  // helper class. 연결 리스트에 추가되는 원소.
  const Node = function(element) {
  	this.element = element; // 원소
    this.next = null; // 다음 노드를 가리키는 포인터
  };
  
  let length = 0; // 연결 리스트의 개수. 내부 프로퍼티
  let head = null; // 연결이 시작되는 지점을 참조
  
  // 리스트의 맨 끝에 원소 추가
  this.append = function(element) {
    const node = new Node(element);
    let current;
    
    if (head === null) { // 리스트가 비어있다면
      head = node;
    } else {
      current = head;
      
      while (current.next) { // 마지막 원소를 발견할 때까지 반복문 실행
      	current = current.next;
      }
      
      curent.next = node;
    }
    
    length++;
  };
  
  // 해당 위치에 원소 삽입
  this.insert = function(position, element) {
    if (position < 0 || position > length) return false;
    
    let node = new Node(element),
        current = head,
        previous,
        index = 0;
    
    if (position === 0) {
      node.next = current;
      head = node;
    } else {
      while (index++ < position) {
      	previous = current;
        current = current.next;
      }
      
      node.next = current;
      previous.next = node;
    }
    
    length++;
    
    return true;
  };
  
  // 해당 위치의 원소 삭제
  this.removeAt = function(position) {
    if (position < -1 || position > length) return null;
    
    let current = head,
        previous,
        index = 0;
    
    if (position === 0) { // 첫 번째 원소 삭제
      head = current.next;
    } else {
      while(index++ < position) {
      	previous = current;
        current = current.next;
      }
      
      previous.next = current.next;
    }
    
    length--;
    
    return current.element;
  };
  
  // 원소 삭제
  this.remove = function(element) {
    const index = this.indexOf(element);
    return this.removeAt(index);
  };
  
  // 해당 원소의 인덱스 반환. 존재하지 않을 경우 -1 return
  this.indexOf = function(element) {
    let current = head,
        index = -1;
    
    while (current) {
      if (element === current.element) {
      	return index;
      }
      index++;
      current = current.next;
    }
    
    return -1;
  };
  
  // 링크드 리스트가 비어있는지 여부
  this.isEmpty = function() {
    return length === 0;
  };
  
  // 원소의 개수 반환
  this.size = function() {
    return length;
  };
  
  // 원소의 값 string으로 반환
  this.toString = function() {
    let current = head,
        string = '';
    
    while (current) {
      string += current.element;
      current = current.next;
    }
    
    return string;
  };
  
  // head 값 얻기
  this.getHead = function() {
    return head;
  };
}

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

이중 연결 리스트는 다음 노드와 이전 노드, 2개의 연결 정보를 이중으로 갖고 있는 리스트.

• 양방향으로 리스트 순회가 가능(처음->끝, 끝->처음)

환형 연결 리스트(Circular Linked List)

• 단방향(연결 리스트) 또는 양방향(이중 연결 리스트)의 참조 정보를 갖음
• 마지막 원소의 next가 head(첫 번째 원소)를 가리킴