단일 연결 리스트(Singly Linked List)

• 순서에 따라 다수의 데이터를 저장한다. 그러나 배열과 다른 점은 인덱스가 없다.
• 마치 객체들이 연속으로 연결되어 있는 기차와 같다.
• 각각 요소를 '노드(node)'라고 부른다. string, number와 같은 하나의 데이터를 저장한다.
• 각 노드들은 다음 요소를 가리키는 정보 또한 저장하고 있다.
• 다음 노드가 없을 경우, null을 저장한다.
• head는 연결 리스트의 시작 노드를 가리킨다.
• tail은 연결 리스트의 마지막 노드를 가리킨다.

 

배열은 엘레베이터, 연결 리스트는 계단과도 같다.

 

List	Array
Do not have indexes!	Indexed in order!
Connected via nodes with a next pointer	Insertion and deletion can be expensive
Random access is not allowed	Can quickly be accessed at a specific index

➡ 연결 리스트는 새로운 항목을 추가하거나 기존 항목을 제거할 경우 편리하다. (인덱스 없음)

 

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 = newNode;
				} else {
					this.tail.next = newNode;
					this.tail = newNode;
				}
				this.length++;
				return this;
    }
    pop() {
            if(!this.head) return undefined;
            var current = this.head;
            var newTail = current;
            while(current.next){
                newTail = current; 
                current = current.next; // newTail은 항상 이전 노드를 가리킨다.
            }
            this.tail = newTail;
            this.tail.next = null; // pop
            this.length--;
            if(this.length === 0){
                this.head = null;
                this.tail = null;
            }
            return current;
    }
    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(val){
            var newNode = new Node(val);
            if(!this.head) { // 리스트 길이가 0일 경우
                this.head = newNode;
                this.tail = this.head;
            } else {
                newNode.next = this.head;
                this.head = newNode;
            }
            this.length++;
            return this;
    }
    get(index){
				// 인덱스가 음수이거나 길이보다 같거나 클 경우 null을 반환
        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(index, val){
        var foundNode = this.get(index);
        if(foundNode){
            foundNode.val = val;
            return true;
        }
        return false;
    }
    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(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(){
      var node = this.head;
      this.head = this.tail;
      this.tail = node;

      var next;
      var prev = null; // 초기 tail의 next가 null이기 때문에
      for(var i = 0; i < this.length; i++){
        next = node.next;
        node.next = prev;
        prev = node;
        node = next;
      }
      return this;
    }
		// console.log를 통해 리스트에 있는 노드들을 순서에 따라 배열로 프린트한다. (return X)
    print(){
        var arr = [];
        var current = this.head
        while(current){
            arr.push(current.val)
            current = current.next
        }
        console.log(arr);
    }
}

var list = new SinglyLinkedList()

list.push("HELLO")
list.push("GOODBYE")
list.push("!")
list.push(100)
list.push(201)
list.push(250)
list.push(350)
list.push(999)