이중 연결 리스트 구현

기본적으로는 단일 연결 리스트와 동일하지만 prev가 있어 탐색에 더 용이하 메모리가 더 많이 먹음

노드

자바스크립트 ver.

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

파이썬 ver.

class Node:
    def __init__(self, data):
        self.data = data
        self.prev = None
        self.next = None

push 매소드 만들기

자바스크립트 ver.

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

파이썬 ver.

class DoublyLinkedList:
    def __init__(self):
        self.head = None
        self.tail = None

    def push(self, data):
        if self.head == None:
            self.head = Node(data)
            self.tail = self.head
        else:
            node = self.head
            while node.next:
                node = node.next
            new = Node(data)
            node.next = new
            new.prev = node
            self.tail = new

pop 매소드 만들기

class DoublyLinkedList {
    constructor() {
        this.head = null;
        this.tail = null;
        this.length = 0;
    }
    pop() {
        if (!this.head) return undefined;
        let poppedNode = this.tail;
        if (this.length === 1) {
            this.head = null;
            this.tail = null;
        } else {
            this.tail = poppedNode.prev;
            this.tail.next = null;
            poppedNode.prev = null;
        }
        this.length--;
        return poppedNode;
    }
}

else문에서 poppedNode.prev = null;를 안 해줄 경우 다음과 같은 상황이 벌어질 수 있음.

let a = list.pop()

list.push("100")
list.push("200")

// a의 값도 수정 됨.

shift 매소드 만들기

class DoublyLinkedList {
    constructor() {
        this.head = null;
        this.tail = null;
        this.length = 0;
    }
    shift() {
        if (this.length === 0) return undefined;
        let first = this.head;
        if (this.length === 1) {
            this.head = null;
            this.tail = null;
        } else {
            this.head = first.next;
            this.head.prev = null;
            first.next = null;
        }
        this.length--;
        return first;
    }
}

unshift 매소드 만들기

class DoublyLinkedList {
    constructor() {
        this.head = null;
        this.tail = null;
        this.length = 0;
    }
    unshift(val){
        let newNode = new Node(val);
        if(this.length === 0) {
            this.head = newNode;
            this.tail = newNode;
        } else {
            this.head.prev = newNode;
            newNode.next = this.head;
            this.head = newNode;
        }
        this.length++;
        return this;
    }
}

get 매소드 만들기

싱글 링크드 리스트와 같은 로직으로 할 수 있지만 최적화를 할 수 있음.

예를 들어 index가 1억까지 있다면, 뒤에 있는 index를 찾으려면 1부터 끝까지 가야하겠지만 더블 링크드 리스트의 경우 prev로 뒤에서 부터 찾아갈 수 있음.

 

자바스크립트 ver.

class DoublyLinkedList {
    constructor() {
        this.head = null;
        this.tail = null;
        this.length = 0;
    }
    get(index){
        if(index < 0 || index >= this.length) return null;
        let count, current;
        if(index <= this.length/2){
            count = 0;
            current = this.head;
            while(count !== index){
                current = current.next;
                count++;
            }
        } else {
            count = this.length - 1;
            current = this.tail;
            while(count !== index){
                current = current.prev;
                count--;
            }
        }
        return current;
    }
}

파이썬 ver.

class DoublyLinkedList:
    def __init__(self):
        self.head = None
        self.tail = None

    def search_from_head(self, data):
        if self.head == None:
            return False
    
        node = self.head
        while node:
            if node.data == data:
                return node
            else:
                node = node.next
        return False
    
    def search_from_tail(self, data):
        if self.head == None:
            return False
    
        node = self.tail
        while node:
            if node.data == data:
                return node
            else:
                node = node.prev
        return False

set 매소드 만들기

싱글 링크드 리스트와 같음.

class DoublyLinkedList {
    constructor() {
        this.head = null;
        this.tail = null;
        this.length = 0;
    }
    get(index){
        if(index < 0 || index >= this.length) return null;
        let count, current;
        if(index <= this.length/2){
            count = 0;
            current = this.head;
            while(count !== index){
                current = current.next;
                count++;
            }
        } else {
            count = this.length - 1;
            current = this.tail;
            while(count !== index){
                current = current.prev;
                count--;
            }
        }
        return current;
    }
    set(index, val) {
        let getNode = this.get(index);
        if (getNode) {
            getNode.val = val;
        }
        return this;
    }
}

insert 매소드 만들기

자바스크립트 ver.

class DoublyLinkedList {
    constructor() {
        this.head = null;
        this.tail = null;
        this.length = 0;
    }
    insert(index, val) {
        if (index < 0 || index > this.length) return null;
        if (index === 0) return this.unshift(val);
        if (index === this.length) return this.push(val);

        let newNode = new Node(val);
        let prevNewNode = this.get(index - 1);
        let nextNewNode = prevNewNode.next;

        prevNewNode.next = newNode
        newNode.prev = prevNewNode;
        newNode.next = nextNewNode
        nextNewNode.prev = newNode;
        
        this.length++;
        
        return this;
    }
}

파이썬 ver.

class DoublyLinkedList:
    def __init__(self):
        self.head = None
        self.tail = None

    def insert_before(self, data, before_data):
        if self.head == None:
            self.head = Node(data)
            return True
        else:
            node = self.tail
            while node.data != before_data:
                node = node.prev
                if node == None:
                    return False
            new = Node(data)
            before_new = node.prev
            before_new.next = new
            new.prev = before_new
            new.next = node
            node.prev = new
            return True
            
    def insert_after(self, data, after_data):
        if self.head == None:
            self.head = Node(data)
            return True            
        else:
            node = self.head
            while node.data != after_data:
                node = node.next
                if node == None:
                    return False
            new = Node(data)
            after_new = node.next
            new.next = after_new
            new.prev = node
            node.next = new
            if new.next == None:
                self.tail = new
            return True

remove 매소드 만들기

class DoublyLinkedList {
    constructor() {
        this.head = null;
        this.tail = null;
        this.length = 0;
    }
    remove(index) {
        if (index < 0 || index >= this.length) return null;
        if (index === 0) return this.shift(val);
        if (index === this.length - 1) return this.pop();

        let removedNode = this.get(index);
        let prevRemovedNode = removedNode.prev;
        let nextRemovedNode = removedNode.next;

        prevRemovedNode.next = nextRemovedNode;
        nextRemovedNode.prev = prevRemovedNode;

        removedNode.prev = null
        removedNode.next = null
        
        this.length--;
        return removedNode;
    }
}