[알고리즘] 연결 리스트 (LinkedList)

카테고리 : 알고리즘
태그: cs · 알고리즘 · algorithm · 자료구조 · 연결리스트 · 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