Linked List

2017-09-08

Linked List란?

Linked List는 Array List와는 다르게 엘리먼트와 엘리먼트 간의 연결(link)을 이용해서 리스트를 구현한 것을 의미합니다.
각 element에는 data와 다음 element의 주소를 갖고있습니다.
마지막 element의 주소는 null입니다.

Array vs Linked List

Array는 메모리를 순서대로 할당합니다.
Linked List 메모리를 랜덤으로 할당합니다.
하지만 javascript의 array는 Linked List의 형태로 되어있어 javascript의 array는 정확한 array라고 할 수 없습니다.
javascript의 splice가 Linked List의 구조를 갖고 있기 때문입니다.
Array는 임의 접근(Random Access)이 쉽다.(원하는 장소에 접근이 가능합니다.)
하지만 Linked List는 head에서 순서대로 접근을 해야합니다.
따라서 원하는 장소에 접근을 원한다면 for문을 사용하여 순서대로 원하는 장소까지 접근을 해야 합니다.

메모리 내의 Array와 Linked List의 차이

출처: opentutorials의 자료구조(Linked list)
위 사진처럼 같은 Array의 각 요소(element)들은 메모리의 같은 곳에 모여있습니다.
따라서 이미 선언된 배열보다 요소들이 늘어나게 되면 Array 전체를 다른 메모리 공간의 주소에 새로 저장해주어야 합니다.
하지만 Linked List의 요소들은 메모리의 주소 값이 랜덤으로 할당되기 때문에 요소들이 늘어나게 되도 새로 메모리내 주소에 요소만 새로 할당해주면 됩니다.
하지만 메모리의 주소값들이 랜덤이기 때문에 각 요소들은 다음 요소의 주소값을 갖고 있어야 합니다.

Array와 Linked List 비교

Array	vs	Linked List
Fixed	Size	Dynamic
Hard	Insert	Easy
Hard	Deletion	Easy
Allowed	Random Access	Not allowed
dosen’t need	Extra memory space	required
Array는 크기가 고정되어있지만 Linked List는 크기가 유동적입니다.(메모리 할당의 차이)
Array는 요소를 추가 삭제가 어렵지만 Linked List는 요소를 추가 삭제가 쉽습니다.(Linked List는 요소를 추가하거나 삭제하게 되면 요소의 전과 후의 주소를 연결해주기만 하면 됩니다.)
Array는 요소의 접근이 쉽지만 Linked List는 요소에 접근하는데 어렵습니다.(다음 목차에 설명)
Array는 여유메모리가 필요없지만 Linked List는 여유메모리가 요구됩니다.(Array는 요소들이 정해지면 덩어리로 메모리를 할당하여 주소를 갖고있게 되는데 Linked List는 다음 요소들이 유동적이기 때문에 메모리의 추가 사용이 가능 할 수도 있기때문입니다.)

Array와 Linked List의 속도

Array	vs	Linked List
o(1)	access	o(n)
o(n)	search	o(n)
o(n)	insert	o(1)
o(n)	remove	o(1)
Array는 원하는 요소를 한번에 접근이 가능합니다.
하지만 Linked List 위쪽 설명처럼 요소까지 접근하려면 각 요소마다 다음 요소의 주소를 찾아 접근을 해야합니다.
따라서 속도가 Array에 비해 느립니다.
하지만 요소를 추가 또는 삭제하는 속도는 Linked List가 Array에 비해 빠릅니다.

Linked List를 javascript로 구현

function LinkedList() {
  var Node = function(element){
    this.element = element;
    this.next = null;
  };
  var length = 0;
  var head = null;
  // Linked List에 요소를 추가
  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++;
  };
  // Linked List에 원하는 위치의 요소를 삭제
  this.removeAt = function(position){
    if(position > -1 && position < length) {
      var 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;
    } else {
      return null;
    }
  };
  // Linked List의 요소 사이에 요소를 삽입
  this.insert = function (position, element) {
    if(position >= 0 && position <= length){
      var 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;
    } else {
      return false;
    }
  };
  // Linked List의 요소를 삭제
  this.remove = function (element) {
    var index = this.indexOf(element);
    return this.removeAt(index);
  };
  // Linked List의 위치
  this.indexOf = function (element) {
    var current = head;
        index = 0;
    while (current) {
      if(element === current.element){
        return index;
      }
      index++;
      current = current.next;
    }
    return -1;
  };
  // Linked List가 비었는지 확인
  this.isEmpty = function () {
    return length === 0;
  };
  // Linked List의 사이즈
  this.size = function () {
    return length;
  };
  // Linked List를 문자로 변환
  this.toString = function () {
    var current = head,
        string = '';
    while (current) {
      string += current.element;
      current = current.next;
    }
    return string;
  };
  // Linked List의 헤드(첫 요소)를 확인
  this.getHead = function () {
    return head;
  };
}

CSdataStructure