4.2Singly Linked Lists

Linked List

A data structure that contains a head, tail and length property. Linked lists consist of nodes, and each node has a value and a pointer to another node or null.

배열과 비슷해보이지만, 배열은 인덱스가 있어 해당 인덱스에 즉시 접근(random access) 가능하다면 Linked List는 인덱스가 없어 특정 인덱스에 즉시 접근할 수는 없다. 대신, 처음과 끝이 있으며 각각의 노드들은 값을 가지고, 다음 노드의 위치에 대한 정보(포인터)가 있어 이를 통해 서로 연결된다.

인덱스가 없어서 즉시 접근할 수 없다면 왜 이 데이터 구조를 쓸까? 바로 삽입과 삭제가 저렴하고 편리하기 때문이다. 요소의 삽입/삭제에 따라 인덱스 정보를 모두 바꿔야할 수도 있는 배열과 달리, Linked List는 관련된 앞뒤의 포인터 및 길이 정보만 변경하면 된다.

노드 만들기

Node 클래스를 선언해보자.

javascript
class Node {
  constructor(val){
    this.val = val;
    this.next = null;
  }
}

인스턴스를 만든다면, 이렇게 될 것이다:

javascript
const first = new Node('Hi');
first.next = new Node('there');
first.next.next = new Node('how');
first.next.next.next = new Node('are');
first.next.next.next.next = new Node('you');

... 물론 이렇게 계속 .next를 이어서는 아주 불편할 것이다.

push 메소드로 데이터 추가하기

push 메소드를 도입함으로 보다 쉽게 데이터를 추가할 수 있다.

javascript
class SinglyLinkedList {
  constructor(){
    this.head = null;
    this.tail = null;
    this.length = 0;
  }

  push(val){
    const newNode = new Node(val);
    if(!this.head){
      // head가 없을 때
      this.head = newNode;
      this.tail = this.head;
    } else {
      // 맨 끝에 새 노드 추가
      this.tail.next = newNode;
      // 새 노드를 tail로 지정
      this.tail = newNode;
    }
    this.length++;
    return this;
  }
}

const list = new SinglyLinkedList();
list.push('Hello');
list.push('Goodbye');

pop 메소드로 데이터 제거하기

pop메소드로 리스트의 가장 마지막에 있는 데이터를 제거해보자. 수도코드를 쓴다면 아래와 같이 될 것이다:

• 리스트에 아무 노드도 없다면, undefined 반환
• tail에 도달할때까지 루프
• tail 직전의 노드의 next 프로퍼티를 null로 설정
• tail 직전의 노드를 tail로 변경
• length를 1 감소
• 제거된 노드를 반환

pop은 마지막 노드를 null로 설정해버리면 return 할 수가 없어서 push보다 복잡하다.

javascript
class SinglyLinkedList {
  constructor(){
    this.head = null;
    this.tail = null;
    this.length = 0;
  }

  push(val){
    // ...
  }

  pop(){
    if(!this.head) return undefined;
    let current = this.head;
    let newTail = current;
    while(current.next){
      newTail = current; // 루프 다 돌면 마지막 바로 앞 노드
      current = current.next; // 루프 다 돌면 마지막 노드
    }
    this.tail = newTail;
    this.tail.next = null;
    this.length--;
    if(this.length === 0){
      this.head = null;
      this.tail = null;
    }
    return current;
  }
}

const list = new SinglyLinkedList();
list.push("HELLO");
list.push("GOODBYE");
list.pop(); // "GOODBYE"

shift 메소드로 맨 앞의 데이터 제거하기

shift메소드로 리스트의 가장 앞에 있는 데이터를 제거해보자. 수도코드를 쓴다면 아래와 같이 될 것이다:

• 아무런 노드가 없다면, undefined를 반환
• 현재의 헤드를 변수에 저장
• 현재 헤드의 next 프로퍼티에 있는 값을 새로운 헤드로 지정
• length를 1 감소
• 변수에 저장된, 제거된 헤드를 반환

javascript
class SinglyLinkedList {
  constructor(){
    this.head = null;
    this.tail = null;
    this.length = 0;
  }

  push(val){
    // ...
  }

  pop(){
    // ...
  }

  shift(){
    if(!this.head) return undefined;
    const currentHead = this.head;
    this.head = currentHead.next;
    this.length--;
    return currentHead;
  }
}

const list = new SinglyLinkedList();
list.push("HELLO");
list.push("GOODBYE");
list.shift(); // "HELLO"

unshift 메소드로 맨 앞에 데이터 추가하기

unshift메소드로 리스트의 가장 앞에 데이터를 추가해보자. 수도코드를 쓴다면 아래와 같이 될 것이다:

• 우선 추가할 값을 받아야한다.
• 추가할 값을 가진 노드를 생성한다.
• 리스트에 head가 없다면, head와 tail을 해당 노드로 설정한다.
• 아니라면 새 노드의 next 프로퍼티를 현재 list의 헤드로 설정한다.
• 새 노드를 head 프로퍼티로 지정한다.
• 길이를 1 늘린다.
• 리스트를 반환한다.

javascript
class SinglyLinkedList {
  constructor(){
    this.head = null;
    this.tail = null;
    this.length = 0;
  }

  push(val){
    // ...
  }
  pop(){
    // ...
  }
  shift(){
   // ...
  }
  unshift(val){
    const newNode = new Node(val);
    if(!this.head){
      this.head = newNode;
      this.tail = this.head;
    } else {
      newNode.next = this.head;
      this.head = newNode;
    }
    this.length++;
    return this;
  }
}

const list = new SinglyLinkedList();
list.push("HELLO");
list.push("GOODBYE");
list.unshift("ADDME!"); // 추가되고 리스트 반환

get 메소드로 인덱스에 있는 요소 찾기

get메소드로 리스트의 특정 인덱스에 어떤 요소가 있는지 찾아보자. 수도코드를 쓴다면 아래와 같이 될 것이다:

• 우선 인덱스를 받아야한다.
• 인덱스가 0보다 작거나 리스트의 길이보다 크다면 null을 반환한다.
• 해당 인덱스에 도달할때까지 루프를 돌고, 해당 인덱스에 있는 요소를 반환한다.

javascript
class SinglyLinkedList {
  // 다른 메소드들...
  get(index){
    if(index < 0 || index >= this.length) return null;
    let counter = 0;
    let current = this.head;
    while(counter !== index){
      current = current.next;
      counter++;
    }
    return current;
  }
}

const list = new SinglyLinkedList();
list.push("HELLO");
list.push("GOODBYE");
list.push("!");
list.push("<3");
list.push(":)");
list.get(4); // Node {val: ":)", next: null}

set 메소드로 특정 인덱스에 있는 요소 변경하기

set메소드로 리스트의 특정 인덱스에 있는 요소를 변경하자. 수도 코드를 작성한다면 아래와 같이 될 것이다:

• 우선 인덱스와 값을 받아야한다.
• get이 있으니 써서 원하는 노드를 찾는다.
• 해당 노드가 없다면 false를 반환한다.
• 해당 노드가 있다면 값을 변경하고 true를 반호나한다.

javascript
class SinglyLinkedList {
  // 다른 메소드들...
  set(index, val){
    const foundNode = this.get(index);
    if(foundNode){
      foundNode.val = val;
      return true;
    }
    return false;
  }
}

const list = new SinglyLinkedList();
list.set(4, "!!!"); // true
list.get(4) // Node {val: "!!!", next: Node}

insert 메소드로 특정 인덱스에 요소 삽입하기

insert메소드로 리스트의 특정 인덱스에 요소를 추가하자. 수도 코드를 작성한다면 아래와 같이 될 것이다:

• 우선 인덱스와 값을 받아야한다.
• 인덱스가 0보다 작거나 길이보다 크다면 false를 반환한다.
• 인덱스가 길이와 같다면, 맨 마지막에 push한다.
• 인덱스가 0이라면 unshift한다.
• 인덱스가 그 외라면, get을 써서 요소를 찾되, 해당 요소의 직전 노드(인덱스 -1)를 찾는다.
• 해당 노드의 next 속성을 새 노드로 지정한다.
• 새 노드의 next 속성을 기존에 해당 인덱스에 있던 노드로 지정한다.
• 길이를 1 늘리고 true를 반환한다.

javascript
class SinglyLinkedList {
  // 다른 메소드들...
  insert(index, val){
    if(index < 0 || index > this.length) return false;
    if(index === this.length) return !!this.push(val); // 반환값을 boolean으로 유지하기 위함
    if(index === 0) return this.unshift(val);
    const newNode = new Node(val);
    let prev = this.get(index - 1);
    let temp = prev.next;
    prev.next = newNode;
    newNode.next = temp;
    this.length++;
    return true;
  }
}

const list = new SinglyLinkedList();
list.push(100);
list.push(200);
list.push(400);

list.insert(4, "LAST");

remove 메소드로 특정 인덱스의 요소 제거하기

remove메소드로 리스트의 특정 인덱스의 요소를 제거하자. 수도 코드를 작성한다면 아래와 같이 될 것이다:

• 우선 인덱스를 받아야한다.
• 인덱스가 0보다 작거나 길이보다 크다면 undefined를 반환한다.
• 인덱스가 길이 -1과 같다면, pop한다.
• 인덱스가 0이라면 shift한다.
• 인덱스가 그 외라면, get을 써서 요소를 찾되, 해당 요소의 직전 노드(인덱스 -1)를 찾는다.
• 해당 노드의 next 속성을 기존 next 노드의 next 노드로 지정한다.
• 길이를 1 줄이고 제거한 노드의 값을 반환한다.

javascript
class SinglyLinkedList {
  // 다른 메소드들...
  remove(index){
    if(index < 0 || index >= this.length) return undefined;
    if(index === 0) return this.shift();
    if(index === this.length - 1) return this.pop();
    const previousNode = this.get(index - 1);
    const removed = previousNode.next;
    previousNode.next = removed.next;
    this.length--;
    return removed;
  }
}

reverse 메소드로 리스트 뒤집기

reverse메소드로 리스트를 뒤집어보자. 수도 코드를 작성한다면 아래와 같이 될 것이다:

• head와 tail을 서로 바꾼다.
• next, prev라는 변수를 만든다.
• node라는 변수를 만들고 head 속성을 부여한다.
• 리스트를 루프하며, node 변수의 next와 prev를 쭉 바꾼다.

javascript
class SinglyLinkedList {
  // 다른 메소드들...
  reverse(){
    const node = this.head;
    this.head = this.tail;
    this.tail = node;

    let next;
    let prev = null;

    for(let i = 0; i < this.length; i++){
      next = node.next;
      node.next = prev;
      prev = node;
      node = next;
    }
    return this;
  }
}

Singly Linked Lists의 Big O