[2020. 10. 25 TIL] Data Structure - Linked List

What is a 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.

• head : the beginning of the linked list
• tail : the end of the linked list
• length : the number of nodes

Comparisons with Arrays

Array : 엘레베이터가 있는 빌딩 ( 5층으로 가주세요 → 한번에 가능)

• indexed in order
• Insertion and deletion can be expensive
• Can quickly be accessed at a specific index

Singly Linked List : 엘레베이터가 없는 빌딩 ( 계단을 통해 한층한층 옮겨다님 )

• Do not have indexes
• Connected via nodes with a next pointer
• Random access is not allowed

Linked List 는 Data 의 삽입(insertion)과 삭제(deletion)에 용이하다

Array가 추가와 삭제에 대해 O(n) , linear 복잡도를 갖는 반면, Linked List 는 O(1), constant 시간 복잡도를 갖는다.

단 , 특정 데이터를 연결리스트에서 검색하고자 할 경우, 처음부터 전체 리스트를 훑어야 하며, 이는 O(n) (linear complexity) 의 복잡도를 필요로 합니다.

keyword : 자료의 추가, 삭제를 용이하게 하기 위함.

자원의 사용량 측면에서는 array가 더 효율적임 (linked list는 next 포인터까지 주어져야하므로 ..)

Method

기본세팅

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

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

1. push

Pushing pseudocode

• This function should accept a value
• Create a new node using the value passed to the function
• If there is no head property on the list, set the head and tail to be the newly created node.
• Otherwise set the next property on the tail to be the new node and set the tail property on the list to be the newly created node.
• Increment the length by one

push(val){
        const newNode = new Node(val);

        if (!this.head) {
            this.head = newNode;
            this.tail = this.head;
        } else {
            this.tail.next = newNode;
            this.tail = newNode;
        }
        this.length += 1;
        return this;
    }

2. pop

Popping pseudocode

• If there are no nodes in the list, return undefined
• Loop through the list until you reach the tail
• Set the next property of the 2nd to last node to be null
• Set the tail to be the 2nd to last node
• Decrement the length of the list by 1
• Return the value of the node removed

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 -= 1;
      if(this.length === 0) {
          this.head = null;
          this.tail = null;
      }
      return current;
    }

3. Shift

Shifting pseudocode

• If there are no nodes, return undefined.
• Store the current head property in a variable
• Set the head property to be the current head's next property
• Decrement the length by 1
• Return the value of the node removed

shift(){
      if (!this.head) {
        return undefined;      
      }
      
      let currentHead = this.head;
      this.head = currentHead.next;
      
      this.length -= 1;
      if(this.length === 0){
        this.tail = null;
      }
      return currentHead;

    }

4. Unshift

Unshifting pseudocode

• This function should accept a value
• Create a new node using the value passed to the function
• If there is no head property on the list, set the head and tail to be the newly created node.
• Otherwise set the newly created node's next property to be the current head property on the list
• Set the head property on the list to be that newly created node
• Increment the length of the list by 1
• return the linked list

unshift(val){
        let 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;
    }

5. Get

Retrieving a node by it's position in the Linked List!

Get pseudocode

• This function should accept an index
• If the index is less than zero or greater than or equal to the length of the list, return null.
• Loop through the list until you reach the index and return the node at that specific index

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;
    }

6. Set

Changing the value of a node based on it's position in the Linked List

Set pseudocode

• This function should accept a value and an index
• Use your get function to find the specific node.
• If the node is not found, return false
• If the node is found, set the value of that node to be the value passed to the function and return true

set(index, value){
        let foundNode = this.get(index);
        if(foundNode) {
            foundNode.val = value;
            return true;
        }
        return false; 
    }

7. Insert

Adding a node to the Linked List at a specific position

Insert pseudocode

• If the index is less than zero or greater than the length, return false
• If the index is the same as the length, push a new node to the end of the list
• If the index is 0, unshift a new node to the start of the list
• Otherwise, using the get method, access the node at the index -1
• Set the next property on that node to be the new node
• Set the next property on the new node to be the previous next
• Increment the length
• Return true

insert(index, value) {
        if(index < 0 || index > this.length) {
            return false;
        }
        if (index === this.length) {
            return !!this.push(value);
        }
        if (index === 0) {
            return !!this.unshift(value);
        }

        let newNode = new Node(value);
        let prev = this.get(index -1);
        let temp = prev.next;
        prev.next = newNode;
        newNode.next = temp;
        this.length++;
        return true;
    }

8. Remove

Removing a node from the Linked List at a specific position

Remove pseudocode

• If the index is less than zero or greater than the length, return undefined
• If the index is the same as the length-1, pop
• If the index is 0, shift
• Otherwise, using the get method, access the node at the index-1
• Set the next property on that node to be the next of the next node
• Decrement the length
• Return the value of the node removed

remove(index){
        if(index < 0 || index > this.length) {
            return undefined
        }
        if (index === this.length-1 ) {
            return this.pop();
        }
        if (index === 0) {
            return this.shift();
        }
        
        let previousNode = this.get(index-1);
        let removed = previousNode.next;
        previousNode.next = removed.next;

        this.length--;
        return removed;
    }

9. Reverse

Reversing the Linked List in place!

Reverse pseudocode

• Swap the head and tail
• Create a variable called next
• Create a variable called prev
• Create a variable called node and initialize it to the head property
• Loop through the list
• Set next to be the next property on whatever node is
• Set the next property on the node to be whatever prev is
• Set prev to be the value of the node variable
• Set the node variable to be the value of the next variable

reverse() {
        let 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;
    }

Big O of Singly Linked List

Insertion - O(1)

Removal = It depends.. O(1) or O(n)

Searching - O(n)

Access - O(n)

Recap

• Singly Linked Lists are an excellent alternative to arrays when insertion and deletion at the beginning are frequently required
• Arrays contain a built in index whereas Linked Lists do not
• The idea of a list data structure that consists of nodes is the foundation for other data structures like Stacks and Queues