자료구조 - 선형 자료 구조 with javascript

[선형 자료 구조]

 

스택(Stack) & 큐(Queue)

스택은 흔히 자바스크립트 엔진에서 콜 스택이 제거되는 방식과 동일하다. 마지막으로 삽입된 element가 가장 먼저 제거되는 방식으로 LIFO(Last in, first out) 혹은 FILO(First in, last out) 구조이다. 재귀 알고리즘, 웹 브라우저의 뒤로가기, 실행 취소(undo) 등이 사용된다.

스택의 시간복잡도

• Insertion: O(1)
• Delete: O(1)
• Search: O(N)

JavaScript에서 스택을 구현하는 것은 간단한 배열을 사용하여 O(1)에서 수행할 수 있지만 이를 통해 push pop을 사용하는 경우 대기열은 삽입에 O(1)을 사용하고 최악의 경우 O(n)을 사용해야 합니다.

삽입과 제거 모두에 대해 O(1)에서 대기열을 구현할 수 있는 더 나은 시간 복잡도 접근 방식은 다음과 같이 를 사용하여 수행할 수 있습니다.

class Stack {
	constructor() {
    	this.elements = {};
        this.length = 0;
    }
    push(element) {
    	this.length++;
        this.elements[this.length] = element;
    }
    pop() {
    	const removed = this.elements[this.length];
    	delete this.elements[this.length];
    	this.length--;
        return removed;
    }
    peek() {
    	return this.elements[this.length];
    }
}

큐는 줄서기와 같은 개념으로 FIFO(First in first out)구조이다. BFS, 캐시(Cache), 인쇄 대기열, 콜센터, 프로세스 관리, 티켓 카운터 등이 사용된다.

큐의 시간 복잡도

• Insert : O(1)
• Delete : O(1)
• Search : O(N)

class Queue {
    constructor() {
        this.elements = {};
        this.head = null;
        this.tail = null;
    }
    enqueue(element) {
        this.elements[this.tail] = element;
        this.tail++;
    }
    dequeue() {
        const item = this.elements[this.head];
        delete this.elements[this.head];
        this.head++;
        return item;
    }
    peek() {
        return this.elements[this.head];
    }
    get length() {
        return this.tail - this.head;
    }
    get isEmpty() {
        return this.length === 0;
    }
}

 

배열(Array) & 연결 리스트(Linked List)

배열은 데이터를 물리적 주소에 순차적으로 저장하며(=논리적 주소와 물리적 주소가 같다.) 인덱스를 가지고 있어 바로 접근할 수 있어서 접근 속도가 빠르다.인덱스를 알고 있다면 O(1)의 시간 복잡도로 접근할 수 있다. 삽입과 삭제에 있어서는 O(1)에 접근한 뒤 데이터를 모두 당기거나 밀어야 하므로 시간이 더 걸린다.

어느 원소를 삭제한다고 할 때, 배열이 연속성이 깨져 빈 공간이 생기며 삭제한 원소보다 큰 인덱스를 갖는 원소들을 shift 해줘야하는 cost가 생기며 이 경우 시간 복잡도가 O(n)이 된다. 삽입도 마찬가지로 첫 번째 원소에 삽입한다면 전부 shift 해줘야 하므로 O(n)가 된다. 데이터의 추가/삭제를 위해서 임시 배열을 생성하고 복제하는데 있어 시간이 오래 걸린다.

• 사용하기 간단하다.
• 물리적 주소와 논리적 주소가 일치한다.
• Random Access(무작위 접근)가 가능하다.
• 배열의 처음이나 중간에서 원소를 삽입/삭제 하는데 임시배열을 복제하고 있어 시간이 오래 걸린다.
• 리스트의 크기가 정해져 있는 경우 크기를 재조정하는데 많은 연산이 필요하다.
• 인덱스 기준으로 어디던지 참조가 가능하다.
• 모든 데이터 유형을 저장할 수 있으며, 배열도 포함됩니다. (다차원 배열)

배열

연결리스트는 각 노드가 데이터 필드와 다음 노드에 대한 참조를 포함하는 노드로 구성된 포인터를 사용해 연결하는 리스트. 특정 데이터에 접근할 때 인덱스로 바로 접근할 수 있었던 배열과 달리 첫 노드부터 원하는 노드까지 링크를 따라가야 접근이 가능하기 때문에 접근 속도는 배열에 비해 느리다. 반대로, 데이터를 삽입/삭제 할 때는 물리적 주소에 구애받지 않고 앞/뒤 노드의 주소만 끼워 넣을 주소로 바꿔주면 되기 때문에 삽입/삭제는 배열보다 빠르다.

• 마지막 항목은 NULL을 가리킨다.
• 프로그램이 수행되는 동안 크기가 커지거나 작아질 수 있다.
• 포인터를 위한 메모리가 필요하지만 낭비하는 공간이 없다.
• 연속되는 항목들이 포인터로 연결된다.
• 무작위 접근이 불가능하며 순차적 접근만 가능하다.
• 데이터를 추가하기 위해 새로운 노드를 생성하여 연결하므로 추가/연산이 빠르다.
• 리스트의 크기에 상관없이 데이터를 추가할 수 있다.

 

양방향 연결 리스트

자바스크립트에서, (Singly) 링크드 리스트는 이런식으로 생겼다.

const list = {
    head: {
        value: 6
        next: {
            value: 10                                             
            next: {
                value: 12
                next: {
                    value: 3
                    next: null	
                    }
                }
            }
        }
    }
};

다음과 같이 구현된다.

// Singlely Linked List

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

class LinkedList {
    constructor() {
    	this.head = new Node('init');
    }
    append(newElement) {
        const newNode = new Node(newElement);
        let current = this.head;
        while(current.next !== null) {
            current = current.next;
        }
        current.next = newNode;
    }
    insert(newElement, item) {
        const newNode = new Node(newElement);
        let current = this.find(item);
        newNode.next = current.next;
        current.next = newNode;
    }
    find(item) {
        let current = this.head;
        while(current.element !== item) {
            current = current.next;
        }
        return current;
    }
    remove(item) {
        let prev = this.findPrev(item);
        prev.next = prev.next.next;
    }
    findPrev(item) {
        let current = this.head;
        while(current.next !== null && current.next.element !== item) {
            current = current.next;
        }
        return current;
    }
    toString() {
        let array = [];
        let current = this.head;
        while(current.next !== null) {
            array.push(current.next.element);
            current = current.next;
        }
        return array;
    }
}

let linkedList = new LinkedList();
linkedList.insert("A", "head");
linkedList.insert("B", "A");
linkedList.insert("C", "B");
linkedList.remove("B");
linkedList.append("D");
linkedList.append("E");

console.log(linkedList.toString())

// Doubely Linked List

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

class DoublelyLinkedList {
	constructor() {
    	this.head = new Node('head');
    }
    insert(newElement, item) {
    	let newNode = new Node(newElement);
        let currentNode = this.find(item);
        if(currentNode.next === null) {
        	newNode.next = null;
            newNode.prev = currentNode;
            currentNode.next = newNode;
        } else {
        	newNode.next = currentNode.next;
            newNode.prev = currentNode;
            currentNode.next.prev = newNode;
            currentNode.next = newNode;
        }
    }
    find(item) {
    	let currentNode = this.head;
        while(currentNode.element !== item) {
        	currentNode = currentNode.next;
        }
        return currentNode;
    }
    remove(item) {
    	let currentNode = this.find(item);
        if(currentNode.next !== null) {
        	currentNode.prev.next = currentNode.next;
            currentNode.next.prev = currentNode.prev;
            currentNode.next = null;
            currentNode.prev = null;
        }
    }
}

 

https://boycoding.tistory.com/33

자바스크립트 자료구조 연결 리스트(Linked List)

https://ahribori.com/article/591a5824c686bd0d48e95f47

[자료구조] 배열(Array)과 연결리스트(LinkedList)