데이터 구조 시리즈: 체인 테이블

31883 단어 programminglinkedlistjavascriptdatastructure

소개하다.



우리는 포크로 스파게티를 먹고 숟가락으로 국을 먹고 젓가락으로 만두를 먹는다.모든 은기는 장단점이 있기 때문에 음식과 상호작용이 좋은 상황에서 다른 은기보다 더 잘 작동한다.이와 같이 상황/용례에 따라 서로 다른 데이터 구조가 다른 데이터 구조보다 더욱 적합하고 성능도 더욱 좋다.그것들은 각각 이로움과 폐단이 있다.이러한 장점과 단점을 이해하면 당신이 더 좋은 프로그래머가 되는 데 도움을 줄 수 있다. 왜냐하면 이것은 당신이 자신의 상황/목표에 따라 적당한 데이터 구조를 선택할 수 있고 응용 알고리즘의 성능을 대폭 향상시키는 데 도움이 될 것이다.만약 당신에게 어떤 문제가 있으면 언제든지 평론을 발표하세요!

카탈로그


1. What is Linked List?
2. Implementation in JavaScript
3. Helper Methods
4. Big O
5. Helpful Resources

1. 체인 시계는 무엇입니까?

A Linked List is a collection of data in a sequence, with each of the data referencing its next node (or previous node if it is a Doubly Linked List) from its 'head' to the 'tail'.
체인 테이블은 순서대로 집합하여 표시하는 데이터 형식이다.이 집합의 모든 단락의 데이터를 노드라고 하는데, 이것은 서열의 인접한 노드를 인용한다.체인 테이블의 첫 번째 노드를'머리'라고 하고 마지막 노드를'꼬리'라고 한다.체인 시계는 두 가지 유형이 있는데 그것이 바로 단일 체인 시계와 이중 체인 시계이다.이름과 같이 단일 링크 목록의 노드는 한 방향에서만 링크되기 때문에 모든 노드는 다음 노드를 인용한다.다른 한편, 쌍사슬표의 노드는 상기와 다음 노드를 동시에 인용한다.한 마디로 하면 체인 테이블은 일련의 데이터의 집합으로 모든 데이터는'머리'에서'꼬리'까지 그 다음 노드를 인용한다(쌍체인 테이블이라면 전 노드이다).
그것은 내장된 데이터 구조의 수조처럼 들리지 않습니까?다른 점은 수조가 메모리에서 모든 데이터를 연속적으로 저장하는 데 있는데 이것은 원소가 서로 인접하여 저장된다는 것을 의미한다.모든 요소는 위치 인덱스를 기반으로 하고, 모든 요소는 이 인덱스를 통해 직접 접근할 수 있다.동시에 체인표는 모든 데이터를 메모리의 어느 위치에 저장하지만 노드는 그 다음과 이전 노드를 인용한다.따라서 체인 테이블의 특정 노드에 접근하기 위해서는 찾고자 하는 노드를 찾을 때까지 목록의 머리나 꼬리에서 다른 끝까지 차례대로 이 목록을 옮겨다니야 한다.
이러한 차이로 인해 체인 테이블은 수조보다 더 잘 만들 수 있고 반대로도 마찬가지다.

  • 수조는 더 빨리 검색할 수 있다


    우리가 논의한 바와 같이, 수조는 무작위 접근을 지원하기 때문에, 우리는 (n) 색인에 있는 모든 요소를 신속하게 접근할 수 있고, 체인 테이블은 순서대로 접근할 수 있기 때문에, (n) 노드나 찾고 있는 노드의 값을 처음부터 끝까지 검색해야 하기 때문에, 요소를 검색하는 데 더 많은 시간이 필요하다.

  • 체인 테이블은 더 빨리 삽입/삭제할 수 있다


    그룹의 시작이나 중간에 있는 요소를 삽입하거나 삭제하려면, 연속적인 색인 위치가 바뀌기 때문에 오른쪽에 있는 모든 요소를 이동해야 합니다.따라서, 그룹의 마지막 요소를 삽입하거나 삭제하지 않으면, 그룹에 요소를 삽입하고 삭제하는 비용이 높을 수 있습니다.체인 테이블에 대해 첫 번째 요소와 마지막 요소를 삽입/삭제하는 데는 고정된 시간이 필요합니다. 왜냐하면 우리는 머리/꼬리만 업데이트할 수 있기 때문입니다.그러나 중간에 있는 요소를 삽입하거나 삭제하는 데는 선형 시간이 필요할 수도 있습니다. 한 번에 한 요소를 훑어보아야 목록을 삽입하거나 삭제할 위치를 찾을 수 있기 때문입니다.그러나 업데이트된 후에 나타나는 모든 요소는 필요 없고 인접한 노드만 다시 배열하면 된다.

    • 2. 자바스크립트 구현

    Singly Linked List

    // each node references its NEXT node
class Node {
    constructor(value) {
        this.value = value;
        this.next = null;
    }
}

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

let SLL = new SinglyLinkedList();
let firstNode = new Node(16)
let secondNode = new Node(2)
let thirdNode = new Node(46)

// set the first new node as the SLL's head
SLL.head = firstNode;
SLL.length++;

// second as its next
firstNode.next = secondNode;
SLL.length++;

// the third as the second's next 
// while also setting it as a tail since it's the last one.
secondNode.next = SLL.tail = thirdNode;
SLL.length++;

// This SLL will look something like this:
// (16) => (2) => (46)

    Doubly Linked List

    // each node references both its NEXT and PREVIOUS node
class Node {
    constructor(value) {
        this.value = value;
        this.next = null;
        this.prev = null;
    }
}

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

let DLL = new DoublyLinkedList();
let firstNode = new Node(361)
let secondnode = new Node(99)
let thirdNode = new Node(4)

// set the first new node as the DLL's head
DLL.head = firstNode;
DLL.length++;

// second as its next, and head as its prev
firstNode.next = secondNode;
secondNode.prev = firstNode;
DLL.length++;

// the third as the second's next 
// while also setting it as a tail since it's the last one.
secondNode.next = DLL.tail = thirdNode;
thirdNode.prev = secondNode;
DLL.length++;

// This SLL will look something like this:
// (361) <=> (99) <=> (4)

    We will set up a Node class which accepts a value and set it to its value, with its next property (and prev if Doubly Linked List) initialized to null. Linked List class will be a sequential collection of these nodes, which will have its head and tail. We will want to keep track of the list's length, and increment/decrement it every time a new node is added or removed. Since Singly Linked Lists's nodes only reference the next node and Doubly Linked Lists' nodes reference both their next and previous nodes, Singly Linked Lists are simpler but less powerful than Doubly Linked Lists.

    If you were to implement a helper method to pop the last element of the list, it's easier to do that with Doubly Linked Lists as you simply have to remove the tail of the list, and set the new tail to be the previous node of the tail being removed. On the other hand, we can access the tail of the list, but will have to traverse the entire list and remember the previous node until you hit the tail so you can remove the tail and set the remembered previous node to be the new tail.

    The main drawback of using Doubly Linked List vs Singly Linked List is that Doubly Linked List takes up more space than the Singly Linked List since you have to set each nodes' next and previous node. But in return, it opens up more doors to make your data and its algorithms efficient. With that being said, here are couple helper methods to utilize Linked Lists better. However, we will only focus on Doubly Linked Lists for this blog post.

    3. 지원 방법(듀얼 링크 목록만 해당)

    push()

    // accepts a value as an argument
// appends a new node with the value passed at the end of the list
push(value) {
    let newNode = new Node(value);
    if(!this.head) {
        this.head = this.tail = newNode;
    } else {
        this.tail.next = newNode;
        newNode.prev = this.tail;
        this.tail = newNode;
    }
    this.length++;
    return this;
}

    Pseudo code:

    • Create a new node with the value passed to the function
    • If the head property is null , set the head and tail to be the newly created node
    • If the head is not null , set the next property on the tail to be that node
    • Set the prev property on the newly created node to be the tail
    • Set the tail to be the newly created node
    • Increment the length
    • Return the Linked List

    pop()

    // removes the last node (tail) of the list
pop() {
    if(!this.head) return undefined;
    let removedNode = this.tail;
    if(this.length === 1) {
        this.head = this.tail = null;
    } else {
        this.tail = removedNode.prev;
        this.tail.next = null;
        removedNode.prev = null;
    }
    this.length--;
    return removedNode;
}

    Pseudo code:

    • If there is no head , return undefined
    • Store the current tail in a variable to return later
    • If the length is 1, set the head or tail to be null
    • Update the tail to be the previous Node
    • Set the new tail 's next to null
    • Decrement the length
    • Return the node removed

    unshift()

    // accepts a value as an argument
// prepends a new node with the value passed at the beginning of the list
unshift(value) {
    let newNode = new Node(value);
    if(this.length === 0) {
        this.head = newNode;
        this.tail = this.head;
    } else {
        this.head.prev = newNode;
        newNode.next = this.head;
        this.head = newNode;
    }
    this.length++;
    return this;
}

    Pseudo code:

    • Create a new node with the value passed to the function
    • If the length is 0, set the head and tail to be the new node
    • Otherwise
      • Set the prev property on the head to be the new node
      • Set the next property on the new node to be the head property
      • Update the head to be the new node
    • Increment the length
    • Return the Linked List

    shift()

    // removes the first node (head) of the list
shift() {
    if(this.length === 0) return undefined;
    let oldHead = this.head;
    if(this.length === 1) {
        this.head = null;
        this.tail = null;
    } else {
        this.head = oldHead.next;
        this.head.prev = null;
        oldHead.next = null;
    }
    this.length--;
    return oldHead;
}

    Pseudo code:

    • If length is 0, return undefined
    • Store the current head property in a variable
    • If the length is one, set the head and tail to be null
    • Update the head to be the next of the old head
    • Set the head 's prev property to null
    • Set the old head 's next to null
    • Decrement the length
    • Return old head

    get()

    // accepts an index as an argument
// returns the node at the index passed
get(idx) {
    if(idx < 0 || idx >= this.length) return null;
    let count, current;
    if(idx <= this.length/2 ) {
        count = 0;
        current = this.head;
        while (count !== idx) {
            current = current.next
            count++
        }
        return current;
    } else {
        count = this.length-1;
        count = this.tail;
        while (count !== idx) {
            current = current.prev
            count--
        }
        return current;
    }
}

    Pseudo code:

    • If the index is less than 0 or greater or equal to the length , return null
    • If the index is less than or equal to half the length of the list
      • Loop through the list starting from the head and loop towards the middle
      • Return the node once it is found
    • If the index is greater than half the length of the list
      • Loop through the list starting from the tail and loop towards the middle
      • Return the node once it is found

    set()

    // accepts an index and value as arguments
// finds the node at the index, and updates the node's value to the value passed
// returns false if the node is not found, true if the value is updated
set(idx, value) {
    let foundNode = this.get(idx);
    if(!foundNode) return false;
    foundNode.value = value;
    return true;
}

    Pseudo code:

    • Create a variable which is the result of the get method at the index passed to the function
    • If the get method does not return a valid node, return false
    • Set the value of the node found from get method to the value passed to the function
    • return true

    4. 대O


  • 공간 복잡성:
  • O(n)
  • 이 데이터 구조의 공간 복잡도는 선형이고 목록 크기가 증가함에 따라 공간 복잡도도 선형이다

  • 밀어내기/팝업 및 스왑/스왑 취소:

  • O(1)시간 복잡도
  • 체인 테이블의 시작과 끝에 있는 노드를 추가/삭제하는 데 일정한 시간이 걸립니다. 양쪽에 새 노드를 추가하고 새로 추가된 노드를 헤드/tail로 업데이트하거나 노드를 삭제할 때 이전/다음 요소를 헤드 또는tail로 업데이트하기 때문입니다.

  • 가져오기/설정 및 삽입/삭제:

  • O(n)시간 복잡도
  • 체인 테이블에서 원소를 찾기 위해서는 체인 테이블을 옮겨다니며 색인이나 색인 값을 찾아야 한다.체인 테이블의 이런 성질 때문에 목록 중간의 노드를 수정하는 데는 선형 시간이 필요할 것이다(시간 복잡도는 목록의 크기에 따라 달라진다).비록 위의 helper 방법에는 Insert/Delete 방법이 열거되어 있지 않지만, 요소를 삽입하거나 삭제하기 위해 목록을 훑어보아야만 목록의 인덱스를 찾을 수 있다는 것을 생각하게 될 것입니다.

    • 5. 유용한 자원

    Online Course(내 과정)
    제 수업'자바스크립트 알고리즘과 데이터 구조 대가반'을 보세요!이것은 만들어진 것이다. 나는 이 블로그의 데이터 구조 실현 부분에서 그의 코드를 인용했다.개인적으로 나는 알고리즘과 데이터 구조, 특히 비기술적 배경에서 온 알고리즘과 데이터 구조를 어디서부터 배우기 시작했는지 모르겠다.이 과정의 구조는 매우 좋아서 초보자는 이런 주제에 기초를 닦을 수 있다.
    Visual Animation(시각 알고리즘)
    어떤 사람들에게는 코드/텍스트만 봐도 데이터 구조를 이해하기 어렵다.상기 과정의 강사는 VisuAlgo라는 사이트를 사용하는데 이 사이트는 애니메이션을 통해 알고리즘과 데이터 구조를 직관적으로 보여준다.
    Data Structure Cheat Sheet(면접 케이크)
    그 밖에 데이터 구조에 대한 아주 좋은 총결산 메모지/가시화도 있다.
    대상 Linux Master ~ su 명령에 대한 권한 ~
    TIL : ) 로그인 활성화하기

    좋은 웹페이지 즐겨찾기

    개발자 우수 사이트 수집

    개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
    best100-homepage