안녕하세요, 이것은 자바스크립트 데이터 구조와 알고리즘에 관한 시리즈 블로그의 5.1 부분입니다. 이 블로그에서 체인 테이블을 소개하겠습니다.

체인 시계는 무엇입니까?

A linked list consists of nodes where each node contains a data field and a reference(link) to the next node in the list. - geeksforgeeks.org

사용 가능한 작업 목록

밀어넣기: 체인 테이블의 끝에 요소를 삽입합니다.

삽입: 체인 테이블의 주어진 인덱스에 요소를 삽입합니다.

삭제: 체인 테이블의 끝 요소를 삭제합니다.

제거: 체인 테이블이 지정한 인덱스에 있는 요소를 제거합니다.

GetElementAt: 체인 테이블의 색인에 대한 요소를 가져옵니다.

IndexOf: 체인 테이블의 요소에 대한 색인을 반환합니다.

자바스크립트에서의 체인 테이블 구현

두 가지 속성 데이터로 ES6 클래스 노드를 정의하고,
데이터 속성은 보존됩니다. 체인 테이블에 삽입된 데이터와 다음 속성은 보존되고 다음 노드의 지침을 가리킵니다.체인 테이블은 다음 포인터가 서로 연결된 노드 체인일 뿐입니다.바늘이 뭐예요?포인터는 위의 그림과 같이 목록의 다음 구성원을 가리킨다.

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

이제 세 가지 속성을 가진 ES6 클래스 체인 테이블을 정의합니다.
계산은 체인 테이블의 디지털 요소를 추적합니다.머리는 항상 체인 테이블의 시작 노드를 가리키지만, 처음에는 정의되지 않고 체인 테이블의 두 노드를 비교하는 것과 같다.단일 체인 테이블에서 우리는 머리 노드에 대한 인용만 있을 뿐이다.그래서 체인 시계를 두루 훑어봐야 한다. 우리는 항상 머리부터 시작해서 그것을 두루 훑어본다.그래서 다음 방법은 항상 머리부터 시작한다.

class LinkedList {
    constructor(func) {
        this.count = 0;
        this.head = undefined;
        this.equalFunc = func || defaultEq;
    }
}

밀다

체인 테이블 끝에 요소를 추가할 때 다음과 같은 두 가지 경우가 있습니다.

제목이 정의되지 않으면 체인 테이블이 비어 있습니다.

체인 시계가 비어 있지 않을 때, 우리는 끝에 추가해야 한다.

우선, 우리는 노드 전달 요소를 그 값으로 만듭니다. 만약 head가 정의되지 않았다면, head를 노드 ({1}) 에 분배합니다. 그렇지 않으면, 체인 테이블의 끝에 도달할 때까지, 노드의next가null ({2}) 일 때, 노드를 끝낸next를 노드 ({3}) 에 분배하고, 원소를 추가한 후에count 변수 ({4}) 를 추가합니다.

push(element) {
        const node = new Node(element);
        let current = this.head;
        if (this.head == undefined) {
            this.head = node;  //1
        }else{
            while (current.next != null) { //2
                current = current.next
            }
            current.next = node; //3
        }
        this.count++ //4;
        return;
    }

GetElementAt 회사

색인을 통해 요소를 얻기 위해서, 우리는 먼저 변수 노드를 정의하고, 헤드 ({1}) 를 인용하며, 색인의 경계 오류를 검증합니다. 검사를 통해 색인이며, 0보다 크고count보다 작습니다.({2}); 없으면 정의되지 않은 ({5}) 을 되돌려줍니다. 이제 0부터 체인 테이블을 인덱스 ({3}) 로 교체하고 노드 ({4}) 로 되돌려줍니다.이 방법은 체인 테이블의 모든 위치에 있는 요소를 삽입하고 삭제할 때 매우 유용하다.

  getElementAt(index) {
        let node = this.head; // 1
        if (index >= 0 && index < this.count) { //2
            for (let i = 0; i < index; i++) { //3
                node = node.next;
            }
            return node; //4
        }
        return undefined; //5
    }

삽입

주어진 위치에 요소 삽입하기;색인은 0보다 크고count보다 작아야 합니다. 두 가지 상황이 있습니다.
우리는 우선 변수 노드를 정의할 것이다. 이 노드는 머리를 가리킨다.

인덱스 0({1})

헤드가 정의되지 않았는지 확인

정의되지 않으면 머리가 노드와 같음

그렇지 않으면 헤드 노드를 새 노드로 변경하고 노드의 다음 노드를 이전 헤드로 변경합니다.

인덱스가 0보다 큽니다({2})

목록의 중간이나 끝에 요소를 추가합니다.우선, 우리가 필요한 위치에 도달할 때까지 목록에서 순환해야 한다.이런 상황에서 우리는 색인-1로 순환할 것이다. 이것은 우리가 새로운 노드를 삽입하기를 희망하는 위치 이전의 한 위치

를 의미한다

우리가 순환을 종료할 때, 이전 변수는 색인 이전의 요소를 인용하고, 우리는 그 안에 새로운 요소와 현재 변수를 삽입해야 한다.

우선, 우리는 노드의 다음 링크를 현재에 연결한 다음에 이전과 현재 사이의 링크를 변경합니다.우리는 이전이 필요하다.노드 옆.

insert(element, postion) {
        if (postion >= 0 && postion <= this.count) {
            const node = new Node(element);
            let current = this.head;
            if (postion == 0) { //1
                if (this.head == undefined) {
                    this.head = node;
                }
                this.head = node;
                node.next = current;
            } else {  
                let previous = this.getElementAt(postion - 1);
                current = previous.next;
                node.next = current;
                previous.next = node;
            }
         this.count++;
        }
    }

전체 소스를 얻을 수 있습니다 here

결론:

방법
복잡성
모든 위치에 삽입
O(n)
머리에 삽입
O(1)
GetElementAt 회사
O(n)
그래서 다음 블로그에 계속 관심을 가져 주십시오. 그 중에서 나머지 방법을 소개하겠습니다.