13 단일 연결 리스트

13.1 단일 연결 리스트 소개(Singly Linked Lists)

  단일 연결 리스트는 연결 리스트의 한 종류로 문자열, 숫자 등 무엇이든 원하는 데이터를 저장하는 자료 구조다. 단일 연결 리스트는 데이터와 데이터의 연결이 한 쪽 방향으로만 연결되는 자료 구조다. 배열처럼 순서에 따라 다수의 데이터를 저장한다. 하지만 배열과의 큰 차이점이 있다. 배열의 경우 각 데이터 요소들은 위치가 지정된다. 즉, 배열은 인덱스가 부여된다.  새로운 데이터 요소를 추가할 때 마다 배열은 그 위치에 따른 인덱스가 주어진다. 반면 연결 리스트들은 다음 데이터 요소를 가리키는 인덱스 없이 그냥 다수의 데이터 요소들로 구성되며 데이터에 접근하기 위해 사용할 인데스는 없다.

 

  따라서 연결 리스트들은 다수의 노드들로 구성되고 각 노드는 문자열 혹은 숫자와 같은 하나의 데이터를 저장한다. 각 노드들은 다음 노드를 가리키는 정보 역시 저장하고 있어야 하며 더 이상 다음 노드가 없을 경우 null을 저장하게 된다. 중요한 점은 연결 리스트는 중간에 있는 노드들을 하나 하나 다 추적하지 않는다. 헤드 노드가 어디 있는지만 알고 있을 것이며 헤드 노드부터 다음 두 번째 노드를 알아내고, 두 번째 노드에서 세 번째 노드를 알아 내는 방식으로 마지막 테일 노드까지 접근하게 된다. 연결 리스트를 용이하게 활용하기 위해 마지막 세 번째 프로퍼티로 연결 리스트의 '길이'를 계속 유지하여 활용하면 좋다.

 

★단일 연결 리스트의 특징 정리

1.  단일 연결 리스트는 인덱스를 가지고 있지 않다. 대신 단순히 첫 노드임을 의미하는 헤드 노드와 끝 노드임을 의미하는 테일 노드를 가질 뿐이다.

2. 원하는 노드를 찾을때, 새로운 노드를 추가할 때는 헤드 노드부터 시작하여 하나씩 계속 이동하여 노드를 찾거나, 노드를 추가하면 된다.

3. 각 노드는 next 포인터(프로퍼티)를 통해 연결되어 있으며 이는 임의 접근이 허용되지 않는다는 것을 의미한다.(원하는 지점 바로 접근 불가)

4. 새로운 항목을 추가하거나 기존 항목을 제거할 경우 연결 리스트를 사용하면 매우 효율적임(배열의 맨 뒤의 요소를 제거하거나 추가하는 경우를 제외하고는 배열은 인덱스가 다 변경되어야 하지만 연결 리스트의 경우 인덱스가 없기 때문에 그렇게 할 필요가 없다.)

 

※용어 정리

1. 헤드 : 연결 리스트의 시작 노드를 가리킨다.

2. 테일 : 연결 리스트의 마지막 노드를 가리킨다.

 

13.2 단일 연결 리스트와 데이터 추가, 삭제 메서드 구현하기

class Node{
    constructor(val){
        this.val = val; // 데이터를 저장
        this.next = null; // next프로퍼티에 다음 저장할 데이터를 가리킴(단일 연결하는 것임)
    }
}

class SinglyLinkedList{
    constructor(){
        this.head = null; //헤드 포인터
        this.tail = null; //테일 포인터
        this.length = 0; // 총 길이
    }
}

  데이터를 저장할 노드 클래스를 만들고, 단일 연결 리스트는 헤드, 테일, 그리고 노드의 길이를 나타내는 프로퍼티를 만들어 준다. 

 

13.3 push 메서드 구현

  단일 연결 리스트를 만들고, 리스트에 추가할 노드를 만들었으니 이제 push 메서드를 구현하여 단일 연결 리스트에 맨 마지막에 노드를 추가하는 기능을 만든 것이다.(배열의 push 메서드와 동일한 기능을 하게 구현) 단일 연결 리스트의 마지막에 노드를 추가하고 테일이 가리키는 것을 마지막 노드로 바꿔주고 연결 리스트의 길이를 하나 늘려줘야 한다는것을 주의해야 함

 

13.4 pop 메서드 구현

  push메서드와 대응되는 맨 뒤에 위치하는 노드를 제거하는 기능을 하는 pop메서드다.(배열의 pop메서드와 동일한 기능을 함) push 메서드와 반대로 길이를 하나 줄여주고, 테일을 제거한 노드의 바로 앞 노드로 옮겨줘야 함. 중요한 점은 단일 연결 리스트이기 때문에 헤드에서 출발해서 맨 끝에 있는 노드를 찾아야 한다.

 

13.5 shift 메서드 구현

  단일 연결 리스트의 가장 앞에 있는 노드를 삭제하는 기능을 한다. 리스트 맨 앞에 무엇이 있던지 shift 메서드는 그것을 제거한다. 이는 현재 헤드가 가리키고 있는 노드를 제거한 후 헤드를 원래 헤드가 가리키고 있던 리스트의 두 번째 노드를 가리키도록 한다는 것을 의미한다.

이덱스 모두를 다시 수정해야 하는 배열과 다르게 리스트 길이와 관계없이 항상 동일한 시간에 처리할 수 있다.

 

13.6 unshift 메서드 구현

  단일 연결 리스트의 가장 앞에 새로운 노드를 추가하는 기능을 한다. 즉 새로운 노드를 맨 앞에 추가하고 헤드를 새로 추가한 노드로 바꿔주는 것이다. 만약 헤드가 없을 경우에는 헤드와 테일 모두 새로운 노드를 가리키도록 설정한다. 

 

13.7 get 메서드 구현

 get메서드는 위치를 의미하는 숫자를 인수로 받아서 주어진 위치에 있는 노드를 반환하는 기능을 하는 메서드다. 예를 들어 0을 인수로 주면 첫 번째 노드인 헤드를 반환하게 된다. 중요한 점은 주어진 숫자 만큼 리스트를 따라간 후 해당 위치의 노드를 반환한다는 것이다. 따라서 이것은 배열과 비교했을때 효율적인 메서드는 아니다. 인덱스가 없기 때문에 이동하는 횟수를 추적하는 counter 변수를 만들어 이동할 때마다 counter 변수를 증가시켜 추적한다.

 

13.8 set 메서드 구현

  set 메서드는 두 개의 인수를 전달 받는다. 첫 번째 인수는 위치를 나타내는 값, 두 번째 인수는 해당 위치의 노드의 value를 갱신할 값을 받아 해당 위치의 노드의 value를 수정한다. 이 과정에서 해당 위치에 있는 노드를 찾아내야 하기 때문에 get 메서드를 활용한다. 

 

13.9 insert 메서드 구현

  insert 메서드는 set 메서드와 같이 인덱스와 값을 인수로 받아들인다. 하지만 이미 존재하는 노드를 갱신하는 대신 주어진 노드를 그곳이 어디든 주어진 위치에 새롭게 삽입하는 것이다. 인수로 받은 위치에 있는 노드와 인수로 받은 위치에 있는 노드의 전 노드 사이에 새로운 노드를 추가해야 한다. 이 과정에서 해당 위치에 있는 노드를 찾아내야 하기 때문에 get 메서드를 활용한다. 

 

13.10 remove 메서드 구현

  remove 메서드는 위치를 나타내는 값을 인수로 받아서 해당 위치에 있는 노드를 제거하고 제거된 노드의 전 노드와 다음 노드를 연결시켜주는 기능을 한다. 만약 제거되는 노드가 맨 앞에 위치한 노드인 경우에는 shift 메서드를 활용하고 맨 뒤에 위치한 노드인 경우에는 pop 메서드를 활용한다. 그렇지 않은 경우 인수로 받은 위치의 노드를 찾기 위해 get 메서드를 활용한다.

 

13.11 reverse 메서드 구현

  reverse 메서드는 노드의 순서를 뒤집는 기능을 한다. 리스트 내의 노드의 위치르리 역으로 바꿔주는 것이다. 헤드를 테일로 만들고, 기존헤드의 next가 반대로 새로운 테일을 가리키도록 만들어 준다.

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 자체가 노드임;;이건 노드 연결임//그래서 next프로퍼티를 갖을 수있는거임
            this.tail = newNode; // 여기서는 list 객체의 테일이 뭔지 알기 위해 저장(객체 자체가것을 가리킴)
        }
        this.length++;
        return this;
    }



/*
객체 생성
노드 생성(헤드,<-테일)   
    next : 노드 생성 (<-테일) 
               next : 노드 생성 (<-테일) 
                      next : 노드 생성 (<-테일) 테일이 마지막으로 저장된 노드를 가리키므로 tail.next에 접근 가능

즉, 리스트가 비어있는 하나의 특별한 케이스가 있고(헤드와 테일이 같은 노드를 가리킴)
비어 있지 않은 경우 현재의 테일을 이용한다.(this.tail.next)

리스트의 프로퍼티와 노드의 프로퍼티를 정확하게 구분해서 보면 이해가 쉬움
이 리스트에는 수 백만의 항목들이 저장되어 있더라도 push()는 아주 빠르게 동작한다.
단지 테일을 이용해 리스트의 마지막에 새로운 노드를 추가하고
테일을 맨 끝을 가리키도록 한 자리 움직여 주기만 하면 되기 때문이다.
*/

    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){ // 리스트에 하나의 노드만 남겨져 있을 경우는 특별한 케이스가 되어 null을 따로 추가해줘야함
            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.head.next는 null 값을 가지고 있으므로
            this.tail = null; //this.head까지 다시 null 값을 할당해 줄 필요 없음
        }
        return currentHead;
    }
    
    unshift(val){
        var 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;
    }
    
    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(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 current = this.head;
        this.head = this.tail;
        this.tail = current;
        var next;
        var prev = null;
        for(var i = 0; i < this.length; i++){
            next = current.next; // 현재 노드의 next 프로퍼티가 가리키는 값을 next 변수에 담고 
            current.next = prev; // 현재 노드의 넥스트 프로퍼티가 prev 노드를 가리키게 하는것
            //node.next로 먼저 next변수에 값을 줘서 정보를 저장해놓고, 그 다음에 이제 node.next의 값을 prev변수로  변경하는것임!!
            //한마디로 next 변수는 길잡이 역할 node가 갈 길을 미리 길터놓고, node 변수가 편하게 
            //node변수의 노드의 next 프로퍼티를 편하게 prev노드를 가리키게 만들어 줌
            prev = current;
            current = next; //여기까지 보면 current와 next 변수에 들어있는 노드가 같이 있음
            //그러다가 그 다음 반복문때 next가 다음 노드로 넘어가게됨
    }
    return this;
}