JavaScript에서 체인 테이블의 실현 및 Leetcode 면접 문제 해결

소개하다.

컴퓨터 과학에서 데이터 구조는 데이터 조직, 관리와 저장 형식으로 효율적인 접근과 수정을 실현할 수 있다.데이터 구조는 대량의 데이터를 효과적으로 관리하는 방법을 제공하여 대형 데이터베이스와 인터넷 인덱스 등의 용도에 사용한다.
여러 가지 유형의 데이터 구조가 있는데, 수조, 체인 테이블, 기록, 병합, 두 갈래 나무와 그림을 포함한다.
본고에서 우리는 체인 시계, 그 실현, 우리가 체인 시계에서 집행할 수 있는 각종 방법, 그리고 인터뷰 문제를 소개할 것이다.

무엇이 체인 시계입니까?

체인 테이블도 목록이라고 하는데 노드라고 불리는 원소의 선형 집합이다.노드는 모든 데이터 형식(기본 또는 비기본)이 될 수 있습니다.각 노드에는 값이 있으며 링크 목록의 다음 노드를 가리킵니다.i, e 노드는 다음 노드를 안다.

체인 테이블은 수조에 버금가는 두 번째 큰 데이터 구조로 수조와 유사하다.체인 테이블의 입구점은 헤드라고 하고, 마지막 노드는null을 가리킨다.만약 체인 시계가 비어 있다면, 머리는 비어 있다.

체인 테이블 유형

체인 테이블에는 three의 기본 유형이 있습니다. 즉,

단일 체인 테이블: 이것은 가장 간단한 유형으로 각 노드마다 하나의 데이터와 다음 노드를 가리키는 바늘이 있다.그것은 한 방향에서 데이터를 훑어볼 수 있도록 허용한다.

쌍체인표: 이것은 복잡한 유형으로 그 중에서 각 노드마다 하나의 데이터와 두 개의 앞의 노드와 다음 노드를 가리키는 지침이 있다.데이터의 범람은 양방향이다.

순환 체인 테이블: 이것은 단일 체인 테이블과 유사하고 마지막 노드가 첫 번째 노드를 가리키며 반대로도 마찬가지다.원형과 비슷한 목록을 훑어볼 때, 우리는 모든 노드에서 시작하여, 모든 방향에서 같은 노드에 도달할 때까지 목록을 앞뒤로 훑어볼 수 있다.따라서 순환 체인 시계는 시작점도 끝점도 없다.

왜 체인 시계를 사용합니까?

array와 같이linkedlist는 선형 데이터 구조로 데이터 추가, 삭제, 삽입 등 모든 작업을 수행할 수 있다.다음은 체인 테이블의 장점입니다.

삽입 및 삭제: 그룹의 첫머리에 요소를 추가하여 항목을 다시 배열하고 색인을 이동합니다. 이것은 대형 데이터베이스를 처리할 때 매우 번거로울 수 있습니다.체인 테이블에서, 우리는 노드의 다음 바늘

의 주소만 업데이트할 수 있다

크기: 체인 테이블의 노드가 다음 노드를 알고 있기 때문에 데이터는 분산된 주소에 존재할 수 있다. 이것은 동적 크기가 실행할 때 변화하는 것을 허용하고 수조처럼 데이터를 실행할 때 변경할 수 없는 비분산 메모리 블록에 저장하지 않는다.

메모리 분배: 수조에 대해 메모리 분배는 컴파일할 때 완성되고, 즉 수조를 설명할 때 완성된다.체인 테이블에 대해 데이터가 체인 테이블에 추가될 때 메모리를 분배하여 실행할 때 완성할 수 있다.

메모리 낭비: 체인 테이블의 메모리 분배는 실행할 때 완성되기 때문에 메모리 낭비가 없다.그룹에서, 성명 크기가 100이고, 데이터만 80으로 저장합니다.남은 20개의 공간이 낭비되었다.

실현: 창고와 대기열 등 선형 데이터 구조는 보통 체인 테이블로 쉽게 실현할 수 있다.

체인 테이블의 한계성

메모리 이용률: 데이터를 저장하고 목록의 다음 노드를 가리키는 메모리가 필요하다.Linkedlist는 배열에 비해 메모리가 더 필요합니다.

검색 작업: 체인 테이블에서 유사한 요소의 인덱스에 직접 접근할 수 없습니다.그것은 전체 목록을 훑어보는데, 이것은 시간 낭비를 초래할 수 있다.

메모리 낭비: 쌍체인표에서 역방향으로 옮겨다니는 것은 가능하다. 즉, 노드가 앞과 앞의 요소를 알고 있다는 것이다.사용하지 않으면 추가 메모리와 낭비가 필요하다.

체인 테이블과 수조의 시간 복잡성과 큰 O 기호!

구현 체인 테이블

구조 함수에서 LinkedList와 head를 tail로 초기화하고 길이를 0으로 초기화합니다.

목록에 클래스를 사용하여 노드를 만들 것입니다.이것은 null 키워드를 사용하여 접근할 수 있습니다.

종합하다

일부 Linkedlist 방법

Prepend(): 이 메서드는 목록의 시작 부분에 노드를 추가합니다.

printData(): 목록의 모든 노드를 인쇄합니다.노드, 포인터 및 다음 노드를 표시합니다.

append (): 이 방법은 새 노드를 체인 테이블의 마지막 노드로 추가합니다.

getLength(): 목록의 길이를 반환합니다.

find (): 이 방법은 매개 변수로 전달되는 노드를 찾습니다.찾을 수 없으면 로 돌아갑니다new.

delete(): 매개 변수에서 인용된 노드를 삭제합니다.

code snippets available on

• code pen
• github

LetCode 인터뷰

Question 1

문제 1의 해결 방법

해석하다
링크dlist의 노드를 삭제하려면 포인터를 목표 앞의 다음 노드로 이동해야 합니다.

 node.val = node.next.val ;

Basically saying, where we have 5 as the val, replace it with next val which is 1. this remove 5 from the node.

node.next = node.next.next;

here, our node is an array, [4,5,1,9]. our node.next.next will be [1,9]. This delete the node and its value.

요약

본고에서 우리는 null, 서로 다른 유형linkedlist, linkedlist에 비해 장점과 한계성, 사용할 수 있는 몇 가지 방법과 leetcode 문제의 해결 방안을 토론했다.
읽어주셔서 감사합니다.
너는 내가 새로운 문장을 발표할 때 통지를 받고 싶니?클릭here
ISIAKA ABDULAHI