연결 리스트 (LinkedList)

1. 연결리스트

동적인 자료구조
배열은 가장 많이 쓰는 자료구조 (크기가 변함)
원소를 배열처럼 차례대로 저장하지만, 원소들이 메모리상에 연속적으로 위치하지 않음
원소가 원소를 가리키는 참조 정보(포인터)가 포함된 Node로 구성

2. 연결리스트 클래스 만들기

1) 연결리스트 생성

function LinkedList() {
  // Node 헬퍼 클래스 정의
  var Node = function (element) {
    this.element = element;
    this.next = null;
  };
}

2) 연결리스트의 프로퍼티 정의

var length = 0; // 원소 갯수
var head = null; // 연결 시작 지점 참조

3) 연결리스트에 필요한 메서드 정리

append('원소’) : 리스트의 끝에 원소 추가
insert() : 해당 위치에 원소 삽입
remove() : 원소 삭제
removeAt() : 해당 위치의 원소 삭제
indexOf() : 해당 원소 인덱스 반환, 존재하지않으면 -1 반환
isEmpty() : 원소가 없으면 True / 원소가 있으면 False
size() : 원소 갯수 반환
toString() : 연결 리스트는 원소를 Node에 담아두기 때문에 원소의 값만 출력하려면 자바스크립트 기본 객체로 부터 상속한 toString 메소드를 재정의 override

4) 연결리스트 클래스 정의

function LinkedList() {
  var Node = function (element) {
    this.element = element;
    this.next = null;
  };
 
  var length = 0;
  var head = null;
 
  this.append = function (element) {};
  this.insert = function (position, element) {};
  this.removeAt = function (position) {};
  this.remove = function (element) {};
  this.indexOf = function (element) {};
  this.isEmpty = function () {};
  this.size = function () {};
  this.toString = function () {};
  this.print = function () {};
}

2) 리스트 끝에 원소 추가하기 (append)

빈 연결리스트 인지 판별
연결리스트에서 마지막 노드의 next는 항상 null이다

function LinkedList() {
  var Node = function (element) {
    this.element = element;
    this.next = null;
  };
 
  var length = 0;
  var head = null;
 
  this.append = function (element) {
    var node = new Node(element),
      current;
 
    if (head === null) {
      // 리스트가 비어 있다면
      head = node;
    } else {
      current = head;
 
      // 마지막 원소를 찾을 때까지 계속 루프 순환
      while (current.next) {
        current = current.next;
      }
      // 마지막 원소를 링크할 수 있게 다음 노드에 할당
      current.next = node;
    }
    //리스트 크기 업데이트
    length++;
  };
}
 
var list = new LinkedList();
list.append(15); // Node: { element: 15, next: null } Length: 1
list.append(10); // Node: { element: 10, next: null } Length: 2