[자료구조] 이중연결리스트

이중연결 연결리스트

• 양방향으로 이어져있다.

• 단일 연결리스트보다 보완된 점은 ?
  만약 맨 마지막 요소를 제거한다고 하면 처음부터 tail을 만나기 전까지 검색을 한 후에 삭제할 수 있고,
  거꾸로 reverse 해야 할 때도 앞에서부터 순차적으로 하나하나 방향을 바꿔줘야해서 번거롭다.
  이를 이중 연결리스트를 사용하면 보완할 수 있다.
  
  
• 단점은?
  단일 연결리스트보다 유연성은 있지만, 메모리를 더 많이 사용하는 단점이 있다.
  단일연결리스트 처럼 다음 것만 저장하는 것이 아니라 이전 것도 저장해야 되기 때문에 메모리를 더 많이 사용한다.
  

코드

기본구조

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

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

메서드

• push

  • 추가할 노드를 만든다.

  • 헤드가 널인지, 길이가 0인지 확인 ( 리스트가 비어있는지 체크 )

  • 리스트에 존재할경우
    - 테일을 찾아서 테일의 next 프로퍼티를 추가할 노드랑 설정한다.
    - 추가할 노드의 prev 프로퍼티를 테일로 설정
    - 테일 프로퍼티를 추가할 노드를 가리키도록 설정

    push(val){
            const newNode = new Node(val);
    
            //이중연결리스트가 비어있을 때 
            if(this.length===0){
                this.head = newNode;
                this.tail = newNode;
            }
            else{
                newNode.prev = this.tail;
                this.tail.next = newNode;
                this.tail = newNode;
            }
    
            this.length++;
    
            return this;
        }

• pop 단일연결리스트와는 다르게 테일(끝) 앞에 있는 요소를 찾아서 next 프로퍼티를 null로 설정해줘야 연결이 끊긴다.

  • 리스트가 비어있을 때 pop 하려고 하면 undefined 반환 (내보낼 값이 없으니까)

  • 리스트가 비어있지 않을 경우
    - 현재 테일을 나중에 출력할 수 있도록 변수에 저장
    - 리스트가 1개라면, head와 tail을 null로 설정
    - 리스트가 2개 이상일 경우
    - 현재 테일을 테일 앞에있는 노드를 가리키도록 설정 (prev)
    - 새로운 테일이 가리키는 노드 next를 null로 설정
    - delete노드의 이전 노드를 null로 설정

    pop(){
            if(this.length===0) return undefined;
            
            
            let deleteNode = this.tail;
    
            if(this.length ===1){
                this.tail = null;
                this.head = null;
            }else{
                this.tail = deleteNode.prev
                this.tail.next =null;
                deleteNode.prev = null;
                
            }
            
            this.length--;
            return deleteNode;
     
        }

• shift(첫번째 제거)

  • 길이가 0인지 헤드가 없는지 둘중에 하나만 체크 / 해당한다며 undefined 반환

  • 길이가 1일경우

    • 테일과 헤드를 null로 설정해야한다.

  • 길이가 1초과일 경우
    - 제거할 노드를 저장해준다.
    - 헤드가 삭제할 헤드의 next를 가리킴
    - 연결을 끊어줌
    - 새로운 헤드의 prev는 null로 설정
    - 삭제할 노드의 next는 null로 설정

    shift(){ //맨 처음 제거
            if(this.length===0) return undefined;
            //if(!this.head) return undefined;
    
            const deleteNode = this.head;
            if(this.length ===1){
                this.tail = null;
                this.head = null;
            }
            else{
                this.head = deleteNode.next;
                this.head.prev = null;
                deleteNode.next=null;   
            }
    
            this.length--;
            return deleteNode;
        }

• unshift (첫번째 추가)

  • 새로운 노드를 만들 값을 인자로 받는다.

  • 리스트가 비어있는경우

    • head와 tail은 추가될 노드를 가리킨다.

  • 리스트가 비어있지 않은 경우
    - 헤드의 prev 프로퍼티가 새로운 노드를 가리킴
    - 추가할 노드의 next는 헤드를 가리킴
    - head는 추가할 노드를 가리킴

    unshift(val){ //맨 처음 추가
            const newNode = new Node(val);
            if(this.length===0){
                this.head = newNode;
                this.tail = newNode;
            }
            else{
                newNode.next = this.head;
                this.head.prev = newNode;
                this.head = newNode;
            }
            this.length++;
    
            return this;
        }

• get (position)

  • index가 음수이거나, length보다 크거나 같을 경우 null 반환

  • 찾을 인덱스의 위치에 따라서 앞에서 갈건지, 뒤에서 갈건지 선택
    - 전체 리스트의 길이의 반보다 position이 작거나 같다면
    - 카운트를 증가하며 앞에서 부터 순회, next (position 만큼)
    - 전체 리스트의 길이의 반보다 position이 크다면
    - 뒤에서부터 순회, prev ( length - cnt -1이 position보다 클 때까지만 )

    get(idx){
            if(idx <0 || idx>=this.length) return null;
    
            let curNode;
            let cnt=0;
            if(idx<=this.length/2){
                curNode = this.head ;
                while(cnt<idx){
                    curNode = curNode.next;
                    cnt++;
                }
            }
            else{
                curNode = this.tail;
    						
                while(idx<this.length-cnt-1){
                    curNode = curNode.prev;
                    cnt++;
                }
            }
            return curNode;
        }

• set

  • get 을 이미 구현했기 때문에, get 을 활용해서 값을 바꿔줄 수 있다.

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

• insert

  • 인덱스가 유효한지 체크, 음수이거나 배열길이보다 큰경우

  • 인덱스가 0 이면 unshift 사용

  • index가 length이면 push사용

  • 위의 조건이 모두 아니라면 get 메서드 사용해서 해당위치에 접근

  • 넣을 위치의 앞에 있는 위치의 노드를 찾아냄 get(idx-1)

    insert(idx,val){ // 특정 위치에 넣기
    
            if(idx<0 || idx>this.length) return false;
            if(idx===0) return this.unshift(val);
            if(idx === this.length) return this.push(val);
            
            let newNode = new Node(val);
            let prevNode = this.get(idx-1);
            let nextNode = prevNode.next;
    
            if(prevNode){
                
                prevNode.next = newNode, newNode.prev = prevNode;
                newNode.next = nextNode, nextNode.prev = newNode;
                this.length++;
    
                return true;
            }
            return false;
        }

• remove

  • 인덱스가 유효한지 확인, 음수이거나 배열길이와 크거나 같은 경우

  • index가 0이면 shift() 사용

  • index가 length-1이면 pop()사용

  • 위의 조건이 아니라면, get()메서드를 사용해서 제거한다.
    - 제거할 노드를 변수에 담아준다.
    - 제거할 노드의 prev의 next가 제거할 노드의 next를 가리키게한다.
    - 제거할 노드의 next의 prev가 제거할 노드의 prev를 가리키게한다.
    - 제거할 노드의 next와 prev는 null로 한다.
    - 길이를 감소하고 제거된 노드를 반환한다.

    remove(idx){
            if(idx<0 || idx>=this.length) return undefined;
    
            if(idx===0) return this.shift(idx);
            if(idx===this.length-1) return this.pop();
    
            let deleteNode = this.get(idx);
            
            let prevNode = deleteNode.prev;
            let nextNode = deleteNode.next;
            prevNode.next = nextNode;
            nextNode.prev = beforeNode;
    
            // deleteNode.prev.next = deleteNode.next;
            // deleteNode.next.prev = deleteNode.prev;
    
            deleteNode.prev=null;
            deleteNode.next=null;
    
            this.length--;
    
            return deleteNode;
        }

---

이중연결리스트 빅오

• 단일연결리스트에서 맨 뒤에 제거하는 경우 처음부터 모두 순회해야함으로 O(N)
• 탐색은 O(N/2)로 만들수 있는 이유는 인덱스의 위치에 따라서 앞에서 순회할지 뒤에서 순회할지 분할해서 접근할 수 있기 때문이다. 최적화는 되었지만 빅오표기법에서는 간단하게 적음으로 O(N)으로 간주한다.

이중연결리스트 vs 단일연결리스트

• 이중연결리스트는 이전 노드를 가리키는 부분 빼고는 단일리스트와 똑같다.
• 이중연결 리스트는 데이터를 반대로 다뤄야 하는 경우 쉽다.
  • 예를들어, 브라우저에서 검색기록을 봐야하는 경우라면 실제로 이중연결리스트를 많이 사용한다.
• 탐색에서 시간을 절반이 걸리기 때문에 성능이 더 좋다.
• 하지만, 이중연결리스트가 추가로 만든 포인터 때문에 메모리를 더 소모하는 약점도 있다.

즉, 이중연결리스트는 일정한 상황에서는 훨씬 좋을 수 있는데, 메모리가 더 많이 사용되어지는 단점도 있다.