가수면

단일 연결 리스트 구현 본문

CS/CS

단일 연결 리스트 구현

니비앙 2023. 5. 23. 22:12

노드 = 데이터(value) + 다음 노드 참조 링크(next)

자바스크립트 ver.

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

파이썬 ver.

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

push 매소드 만들기

자바스크립트 ver.

class SinglyLinkedList {
    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; // tail의 뒤에 새로운 값을 추가하고 
            this.tail = newNode; // tail을 입력된 값으로 변경
        }
        this.length++;
        return this;
    }
}

파이썬 ver.

class SinglyLinkedList:
    def __init__(self):
        self.head = None
        
    def add(self, data):
        if self.head == None:
            self.head = Node(data)
        else:
            node = self.head
            while node.next:
                node = node.next
            node.next = Node(data)

pop 매소드 만들기

class SinglyLinkedList {
    constructor() {
        this.head = null;
        this.tail = null;
        this.length = 0;
    }
    pop() {
        if (!this.head) return undefined;
        // 마지막과 마지막이 될 녀석의 초기값을 head로 설정
        let last = this.head;
        let newTail = last;
        while (last.next) { // 마지막의 다음값이 있으면
            newTail = last; // 마지막이 될 녀석을 마지막으로 바꾸고
            last = last.next; // 원래 마지막은 마지막의 다음값으로 변경
        }
        // 마지막의 다음값이 없으면 아래가 실행 됨
        this.tail = newTail;
        this.tail.next = null;
        this.length--;
        return last;
    }
}

위 코드의 경우 last.next가 없어 head만 남았을 경우 while문이 작동하지 않는다.

따라서 tail.next를 null로 비운 뒤 초기값 head로 세팅 된 마지막과 마지막이 될 녀석을 tail로 바꾸는 작업만 반복되게 된다.

 

그렇기에 head만 남았을 경우의 예외처리를 해줘야 함.

class SinglyLinkedList {
    constructor() {
        this.head = null;
        this.tail = null;
        this.length = 0;
    }
    pop() {
        if (!this.head) return undefined;
        let last = this.head;
        let newTail = last;
        while (last.next) {
            newTail = last;
            last = last.next;
        }
        this.tail = newTail;
        this.tail.next = null;
        this.length--;
        // if문 추가 됨
        if (this.length === 0) {
            this.head = null;
            this.tail = null;
        }
        return last;
    }
}

shift 매소드 만들기

class SinglyLinkedList {
    constructor() {
        this.head = null;
        this.tail = null;
        this.length = 0;
    }
    shift() {
        if (!this.head) return undefined;
        let first = this.head
        this.head = first.next
        this.length--;
        if (this.length === 0) {
            this.tail = null;
        }
        return this
    }
}

unshift 매소드 만들기

class SinglyLinkedList {
    constructor() {
        this.head = null;
        this.tail = null;
        this.length = 0;
    }
    unshift(val) {
        let 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 매소드 만들기

자바스크립트 ver.

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

파이썬 ver.

class SinglyLinkedList:
    def __init__(self):
        self.head = None
        
    def get(self, data):
        node = self.head
        while node:
            if node.data == data:
                return node
            else:
                node = node.next

    def desc(self):
        node = self.head
        while node:
            print (node.data)
            node = node.next

set 매소드 만들기

class SinglyLinkedList {
    constructor() {
        this.head = null;
        this.tail = null;
        this.length = 0;
    }
    get(index) {
        if (index < 0 || index >= this.length) return null;
        let counter = 0;
        let current = this.head;
        while (counter !== index) {
            current = current.next;
            counter++;
        }
        return current;
    }
    set(index, val) {
        let getNode = this.get(index);
        if (getNode) {
            getNode.val = val;
        }
        return this;
    }
}

insert 매소드 만들기

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

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

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

remove 매소드 만들기

자바스크립트 ver.

class SinglyLinkedList {
    constructor() {
        this.head = null;
        this.tail = null;
        this.length = 0;
    }
    remove(index) {
        if (index < 0 || index >= this.length) return undefined;
        if (index === 0) return this.shift();
        if (index === this.length - 1) return this.pop();
        let prevNode = this.get(index - 1);
        let removedNode = prevNode.next;
        prevNode.next = removedNode.next;
        this.length--;
        return removedNode;
    }
}

파이썬 ver.

class SinglyLinkedList:
    def __init__(self):
        self.head = None
        
    def delete(self, data):
        if self.head == None:
            print ("해당 값을 가진 노드가 없습니다.")
            return
        
        if self.head.data == data:
            self.head = self.head.next
        else:
            node = self.head
            while node.next:
                if node.next.data == data:
                    node.next = node.next.next
                    return
                else:
                    node = node.next

reverse 매소드 만들기

예시)

prev <=               => next

100, 200, 300, 400, 500

head                         tail

 

위 예시를 뒤집으려면 아래의 흐름을 따르게 된다.

 

먼저 head와 tail을 바꾸고,

 

100, 200, 300, 400, 500

tail                           head

 

기준이 되는 노드가 있다고 했을 때, 기준 노드의 next는 prev가 되고, prev는 next가 되도록 바꿔줘야 한다.

서로 재할당시켜 바꿔줄 것이기 때문에 next와 prev를 따로 변수로 저장해 놓을 필요가 있다.

class SinglyLinkedList {
    constructor() {
        this.head = null;
        this.tail = null;
        this.length = 0;
    }
    reverse() {
    	// head와 tail을 바꿔준다.
        let targetNode = this.head;
        this.head = this.tail;
        this.tail = targetNode;
        
        // 저장해둘 변수 지정
        let nextNode = null;	// targetNode.next;와
        let prevNode = null;	// targetNode;가 되면 될 것이다
        
        for (let i = 0; i < this.length; i++) {
            nextNode = targetNode.next;	// next를 저장
            targetNode.next = prevNode;	// prev로 저장하기 위해 기존 next 값들을 지움 + 이후 next를 prev로 변경
            prevNode = targetNode;	// prev를 저장
            targetNode = nextNode;	// 기준 노드를 한 칸 앞으로 전진 + 지워진 next 값들을 재할당
        }
        return this;
    }
}

'CS > CS' 카테고리의 다른 글

이진 검색 트리 구현  (0) 2023.05.27
스택, 큐 구현  (0) 2023.05.26
이중 연결 리스트 구현  (0) 2023.05.25
공간 복잡도 계산  (0) 2023.03.02
CS  (0) 2023.02.14
'CS/CS' Related Articles more
Comments