알고리즘 시리즈 - 자료구조 1

이번 포스트에서는 선형 자료구조 중 하나인 링크드 리스트에 대해서 다뤄보겠습니다.

링크드 리스트

링크드 리스트 또는 연결 리스트는 순서를 표현하는 노드들의 집합으로, Javascript의 배열(Array)와 유사한 구조이지만 메모리상의 연속적 위치요소를 갖지 않는다는 차이가 있다. 링크드 리스트에서 가장 중요한 것은 연결이 무엇인가를 파악하는 것 이다.

특징으로는,

• 순회하는 동안 순서에 상관없이 효율적인 삽입, 삭제가 가능
• 연속되는 node들이 link로 연결되어 있음
• 마지막 항목은 null을 가리짐
• 배열(Array)에 비해 추가, 삽입, 삭제가 용이하나 순차적 탐색이 아닌 경우 성능이 떨짐
• 탐색 또는 정렬가 main => Array / 추가, 삭제, 삽입이 main => Linked List

구조

링크드 리스트는 Node 라고 부르는 복수의 요소로 이루어져 있으며 각 노드는 자신의 값인 데이터와 다음 노드의 위치를 참조하고 있는 링크 를 가지고 있으며 일련의 리스트는 아래와 같이 부를 수 있다.

• Head: 링크드 리스트의 시작 node
• Current: 연산의 기준이 되는 node
• Before: Current node의 참조값인 link 값을 가지고 있는 node
• Tail: 링크드 리스트의 마지막 node이며 null을 가리킨다

링크드 리스트 기능 (메서드)

• append(data): 생성 / 리스트에 새로운 node를 추가하면 가장 마지막에 위치함
• insert(index, data): 수정 / 특정 index의 node에 데이터 삽입
• indexOf(data): 조회 / 특정 데이터의 node index를 반환, 존재하지 않는 경우 -1을 반환
• search(data): 조회 / 특정 데이터를 기준으로 node 반환, 존재하지 않는 경우 null 반환
• isEmpty(): 조회 / 리스트의 node 유무 반환
• size(): 조회 / 리스트의 node 개수 반환
• removeAt(index): 삭제 / 특정 위치에 있는 node를 삭제
• remove(data): 삭제 / 특정 값을 가진 node를 삭제

구현

링크드 리스트를 구현해보자. 구현 순서는 아래와 같다.

1. 링크드 리스트의 요소인 Node
2. 노드 생성 기능 (append)
3. 노드 조회 기능 (indexOf, isEmpty, size)
4. 노드 수정 기능 (insert)
5. 노드 삭제 기능 (remove, removeAt)

Node

function Node (data) {
  this.data = data
  this.next = null
}

Node는 링크드 리스트의 요소인 node를 생성하는 생성자 함수로, 내부 property로 node 본인의 값인 data와 다음 node를 참조하기 위한 link를 갖는다.

Linked List

링크드 리스트를 생성할 LinkedList 생성자 함수를 정의하고, 위에서 정의한 구조와 메서드를 구현하기 위해 필요한 property를 정의했습니다.

function LinkedList () {
  this.count = 0
  this.head = null
}

Linked List 메서드 구현

위에서 정의한 LinkedList 생성자 함수 내부에 구현해도 되지만 저는 prototype 속성을 이용해 객체 생성 개념으로 구현해보겠습니다.

노드 생성 기능

링크드 리스트에 노드를 생성하는 기능을 구현했습니다.

LinkedList.prototype.append = function (data) {
  let node = new Node(data)
  let current = null

  if(this.head === null) {
    this.head = node
  } else {
    current = this.head

    while(current.next) {
      current = current.next
    }

    current.next = node
  }

  this.count++
}

var list = new LinkedList(); // 링크드 리스트 객체 생성
list.append(15); // node 생성 및 추가
list.append(23);
list.append(10);

console.log(list) // 링크드 리스트 출력

링크드 리스트에 노드를 생성한다는 것은 새로운 node를 추가하면 가장 마지막에 들어간다는 것 으로, 노드를 생성 및 링크드 리스트에 추가할때는 line 5 ~ line 15 와 같이 리스트에 head가 있는지 없는지 확인해야 한다.

만약 head가 비었다면(null) 선언해주면 되고, 지정되어 있다면 head를 current에 할당해준 후 while 문의 current.next가 null이 될때까지 선회(loop)한 후 line 14 의 current.next의 current는 마지막 노드이며 마지막 노드의 링크 속성인 current.next에 현재 생성됐고 추가될 node의 정보를 할당해준다.

위와 같이 구현한 후 list를 출력하면 아래와 같습니다.

노드 조회 기능

이번에는 링크드 리스트에 삽입한 노드를 조회하는 기능을 구현해보겠습니다. 구현할 조회 메서드는 indexOf, search, isEmpty, size 입니다.

indexOf 메서드를 구현해보겠습니다.

LinkedList.prototype.indexOf = function (data) {
  let current = this.head
  let index = 0

  while(current) {
    if (current.data === data) {
      return index
    }

    index++
    current = current.next
  }

  return -1
}

위 코드는 링크드 리스트 객체에서 인자로 넘겨받은 data를 기준으로 리스트 내 index를 반환하는 함수로 line 4 에서 while 문으로 순회하면서 current.data와 인자 data를 비교한 후 index를 반환한다.

search를 구현해보겠습니다.

LinkedList.prototype.search = function (data) {
  let current = this.head

  while (current.data !== data) {
    current = current.next
  }

  return current
}

위 코드는 링크드 리스트 객체에서 data를 기준으로 node를 조회하는 메서드로, while 문 안에서 current.data의 값과 비교해서 동일할때까지 순회하는 구조입니다.

size 메서드를 구현해보겠습니다.

LinkedList.prototype.size = function (data) {
  return this.count
}

리스트의 크기값을 반환합니다.

isEmpty 메서드를 구현해보겠습니다.

LinkedList.prototype.isEmpty = function (data) {
  return this.count === 0
}

생성자 함수 LinkedList에 의해 생성된 객체의 count property를 이용해 리스트가 비었는지 아닌지 반환한다.

노드 수정 기능

이번에는 링크드 리스트의 특정 index의 node에 데이터를 삽입하는 기능을 구현해보겠습니다. 구현할 조회 메서드는 insert 입니다.

LinkedList.prototype.insert = function (position, data) {
  if (position >= 0 && position <= this.count) {
    let node = new Node(data)
    let current = this.head
    let previous = null
    let index = 0

    if (position === 0) {
      node.next = current
      this.head = node
    } else {
      while (index++ < position) {
        previous = current
        current = current.next
      }
    }

    node.next = current
    previous.next = node
  }

  this.count++
  return node

  return false
}

위 코드는 새로운 node를 생성하고, 특정 위치에 기존 node의 이전과 이후의 node에 연결해주는 메서드이다. position이 0이라면 head를 변경해주면 되고, 그렇지 않을 경우 while 문으로 position까지 선회한 후 이전 node를 나타내는 previous 변수에는 교체 전 node를, current 변수에는 교체 전 node의 다음 node 값을 갖는다. 그리고 while 문이 끝나면 교체해야할 node.next 프로퍼티에 교체대상의 다음 node 값을 할당한 current 변수를 할당하고, 교체대상의 이전 node인 previous.next 프로퍼티에는 새롭게 생성한 node를 할당해준다.

노드 삭제 기능

노드 삭제 기능 ()
마지막으로 링크드 리스트에 삽입한 노드를 삭제하는 기능을 구현해보겠습니다. 구현할 조회 메서드는 remove, removeAt 입니다.

이번에는 removeAt 메소드를 구현해보겠습니다.

LinkedList.prototype.removeAt = function (position) {
  if (position > -1 && position < this.count) {
    let current = this.head
    let previoud = null
    let index = 0

    if (position === 0) {
      this.head = current.next
    } else {
      while (index++ < position) {
        previous = current
        current = current.next
      }

      previous.next = current.next
    }

    this.count--
    current.next = null

    return current.data
  }
  return null
}

위 코드는 특정 index를 기준으로 리스트의 node를 삭제하는 메서드로 먼저 삭제한 node의 index인 position 인자를 검증한 후 Line 7 과 같이 삭제할 index가 head 인지 검증한 후 만약 head라면 다음 node를 head로 할당해주고, 그렇지 않을 경우 while 문으로 선회하면서 삭제할 index의 직전 node에서 멈춘 후 이 node를 previous 변수에 할당하고, previous.next의 값을 current.next.next로 할당해 삭제할 index의 node의 앞과 뒤 node를 이어준다.

이번에는 remove 메소드를 구현해보겠습니다.

LinkedList.prototype.remove = function (data) {
  var index = this.indexOf(data)
  return this.removeAt(index)
}

위 코드는 indexOf 메서드를 이용해 data를 기준으로 node의 index를 조회해 removeAt 메서드로 삭제해준다.

마치며

이번 포스트에서는 알고리즘 시리즈의 자료구조 포스팅 중 첫번째로, 링크드 리스트의 정의와 구조 및 메서드에 공부해봤습니다. 그리고 정의한 구조와 메서드를 구현해봤습니다. 다음 포스트에서는 링크드 리스트와 같이 선형 자료구조 중 하나인 큐에 대해서 공부해보겠습니다.

---

참조

• 링크드 리스트
• ES6 javascript로 자료구조 List 구현하기 (배웠으면 사용해보자!!)
• 자료구조(연결 리스트, linked list)
• 자바스크립트 자료구조 연결 리스트(Linked List)
• [자바스크립트] LinkedList 연결 리스트