단일 연결 리스트

연결 리스트

Head(시작), tail(마지막), length 프로퍼티를 갖는 데이터 구조 [인덱스 없는 객차]

연결 리스트는 nodes를 가지고 있고 각 요소를 node라고 한다. 각 노드는 next 포인터를 통해 연결되어 있고 node에는 값을 담고 있는 '데이터'와 다음 node를 가리키는 '링크' 정보를 저장한다. 데이터에는 다양한 형식을 가질 수 있고, 각 노드들은 다음 노드가 가리키는 정보를 저장하고 있어야 하며, 더 이상 노드가 없을 경우 null을 저장하게 된다.

 

 

[!] 배열은 인덱스가 존재해서 arr[5]이런식으로 바로 접근이 가능하지만 연결 리스트는 접근이 불가능하다.

2개다 고층 아파트인데 배열은 EV가 있지만, 연결 리스트는 EV가 없어서 계단으로 층을 거쳐가며 이동해야 한다.

 

아래 사이트에서 동작을 보면서 코드를 구상해보자

 

[출처] : https://visualgo.net/en/list

Big O

Insertion -> O(1)

Removeal -> 가장 앞에 있는 요소를 삭제하는 경우 O(1) 맨 뒤쪽에 있는 경우 O(n)

Searching -> O(n)

Access -> O(n)

 

push

class Node{
  constructor(val){
    this.val=val;
    this.next=null
  }
}
class SinglyLinkedList{
  constructor(){
    this.head=null
    this.tail=null
    this.length=0
  }
  push(val){
    var newNode=new Node(val)
    if(!this.head){
      this.head=newNode
      this.tail=this.head
    }
    else{
      this.tail.next=newNode
      this.tail=newNode
    }
    this.length++
    return this;
  }
}

var list=new SinglyLinkedList()

pop 

    pop(){
        if(!this.head) return undefined;
        var current = this.head;
        var 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;
    }

shift 

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

unshift 

    unshift(val){
        var newNode = new Node(val);
        if(!this.head) {
            this.head = newNode;
            this.tail = this.head;
        }
        newNode.next = this.head;
        this.head = newNode;
        this.length++;
        return this;
    }

get

    get(index){
        if(index < 0 || index >= this.length) return null;
        var counter = 0;
        var current = this.head;
        while(counter !== index){
            current = current.next;
            counter++;
        }
        return current;
    }

set

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

insert

    insert(index, val){
        if(index < 0 || index > this.length) return false;
        if(index === this.length) return !!this.push(val);
        if(index === 0) return !!this.unshift(val);
        
        var newNode = new Node(val);
        var prev = this.get(index - 1);
        var temp = prev.next;
        prev.next = newNode;
        newNode.next = temp;
        this.length++;
        return true;
    }

remove

    remove(index){
        if(index<0 || index >=this.length) return undefined
        if(index===0) return this.shift()
        if(index===this.length-1) return this.pop()

        var previousNode=this.get(index-1)
        var removed=previousNode.next
        previousNode.next=removed.next
        this.length--;
        return removed
    }

reverse

    reverse(){
        var node=this.head
        this.head=this.tail
        this.tail=node
        var next;
        var prev=null;
        for(let i=0;i<this.length;i++){
            next=node.next
            node.next=prev
            prev=node
            node=next
        }
      return this;
    }

print

    print(){
        var arr = [];
        var current = this.head
        while(current){
            arr.push(current.val)
            current = current.next
        }
        console.log(arr);
    }