[알고리즘] 연결 리스트 (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