데이터 구조 분석: 링크
당신 은 고 드 버그 기 계 를 건설 한 적 이 있 습 니까?없 었 다 면, 정성 들 여 만 든 도미 노 골라인 을 만 들 었 을 까?
그래, 어쩌면 너의 어린 시절 은 나 처럼 책벌레 같 지 않 을 지도 몰라.이렇게 하 자. 상기 두 가지 중에서 똑 같은 것 을 해 본 사람 에 게 너 는 오늘 데이터 구조의 본질 을 파악 했다. 즉, 링크!
체인 시 계 는 어떻게 작 동 합 니까?
체인 테이블 의 가장 간단 한 실현 형식 인 단일 체인 테이블 은 일련의 노드 로 모든 단독 노드 는 하나의 값 과 체인 테이블 의 다음 노드 를 가리 키 는 지침 을 포함한다.
추가 (Add) 는 표 의 끝 에 항목 을 추가 하여 목록 의 크기 를 증가 시 킵 니 다.
제거 (Remove) 는 일반적으로 링크 에서 지정 한 위치의 요 소 를 제거 합 니 다.
검색 (Contains) 은 목록 에서 지정 한 값 을 검색 합 니 다.
사용 예:
이 글 을 가 볍 고 우호 적 으로 유지 하기 위해 서, 우 리 는 다음 시즌 의 '과속 전진' 리얼리티 촬영 을 계획 할 수 있 는 CBS 도 구 를 만 들 었 다.
본문 을 읽 을 때 나 는 네가 계속 자신 에 게 물 어 볼 수 있 기 를 바란다. "링크 와 배열 은 어떤 차이 가 있 습 니까? 그들 은 어떤 비슷 한 점 이 있 습 니까?"
시작 합 시다.
우선, 링크 를 만들어 야 합 니 다:
class LinkedList{
constructor(){
this._head = null;
this._tail = null;
this._length = 0;
}
size(){
return this._length;
}
}
경기 의 출발점 과 종점 을 추적 하기 위해 서 는 head 와 tail 속성 을 만들어 야 합 니 다.
그리고 경기 일정 이 너무 길 거나 짧 지 않도록 length 속성 과 size 방법 을 만들어 야 합 니 다.이렇게 하면 너 는 항상 경기 일정 의 길 이 를 정확하게 파악 할 수 있다.
이제 데 이 터 를 저장 하 는 방법 이 생 겼 습 니 다. 목록 에 데 이 터 를 추가 하 는 방법 을 만들어 야 합 니 다.문 제 는 어떤 데 이 터 를 추가 하 시 겠 습 니까?
기억 하 세 요. 링크 는 일련의 노드 입 니 다. 모든 노드 는 하나의 값 과 목록 의 다음 노드 를 가리 키 는 지침 이 있 습 니 다.이 점 을 알 게 되면 노드 는 value 와 next 두 개의 속성 을 저장 하 는 대상 이라는 것 을 깨 닫 게 될 것 이다.
목록 에 데 이 터 를 추가 할 때마다 새로운 노드 를 만들어 야 하기 때문에 구조 함 수 를 만 들 기로 결 정 했 습 니 다. 목록 에 데 이 터 를 추가 할 때마다 노드 를 만 드 는 것 이 더 간단 합 니 다.
class Node{
constructor(value){
this.value = value;
this.next = null;
}
}
구조 함수 가 있 으 면 add 방법 을 만 들 수 있 습 니 다.
class Node {
constructor(value) {
this.value = value;
this.next = null;
}
}
class LinkedList {
constructor() {
this._head = null;
this._tail = null;
this._length = 0;
}
add(value) {
let node = new Node(value); //we create our node
if(!this._head && !this._tail){ //If it's the first node
this._head = node; //1st node is head & tail
this._tail = node;
}else{
this._tail.next = node; //add node to the back
this._tail = this._tail.next; //reset tail to last node
}
this._length++;
}
size() {
return this._length;
}
}
const AmazingRace = new LinkedList();
AmazingRace.add("Colombo, Sri Lanka");
AmazingRace.add("Lagos, Nigeria");
AmazingRace.add("Surat, India");
AmazingRace.add("Suzhou, China");
현재 이 방법 을 추 가 했 습 니 다. "Amazing Race" 목록 에 경기 장 소 를 추가 할 수 있 습 니 다.이렇게 보 여요.더 쉽게 이해 하기 위해 서 나 는 추가 적 인 빈 칸 을 추가 했다.
{ _head:
{ value: 'Colombo, Sri Lanka',
next: { value: 'Lagos, Nigeria',
next: { value: 'Surat, India',
next: { value: 'Suzhou, China',
next: null
}
}
}
},
_tail: { value: 'Suzhou, China', next: null },
_length: 4
}
자, 이제 목록 을 만 들 고 내용 을 추가 하 는 방법 이 생 겼 습 니 다. 목록 에 장 소 를 추가 하 는 데 방법 이 필요 하 다 는 것 을 깨 달 았 습 니 다.
당신 은 이 링크 를 합작 자, Kent 에 게 공유 하기 로 결 정 했 습 니 다. 그 에 게 더 많은 경기 장 소 를 추가 하 라 고 요구 합 니 다.유일한 문 제 는 목록 을 그 에 게 주 었 을 때 어떤 장 소 를 추 가 했 는 지 알려 주지 않 았 다 는 것 이다.불행 하 게 도 너 도 잊 었 다.
물론 그 는 운행
console.log(AmazingRace) 을 통 해 출력 을 하나하나 검사 할 수 있다.그러나 Kent 는 게 으 른 사람 이다. 그 는 어떤 값 이 목록 에 존재 하 는 지 확인 하고 중복 추 가 를 피 하 는 방법 이 필요 하 다.이 점 을 감안 하여 일부 값 이 포함 되 어 있 는 지 확인 하기 위해 contains 방법 을 만 들 었 습 니 다.class Node {
constructor(value) {
this.value = value;
this.next = null;
}
}
class LinkedList {
constructor() {
this._head = null;
this._tail = null;
this._length = 0;
}
add(value) {
let node = new Node(value);
if(!this._head && !this._tail){
this._head = node;
this._tail = this._head;
}else{
this._tail.next = node;
this._tail = this._tail.next;
}
this._length++;
}
contains(value){
let node = this._head;
while(node){
if(node.value === value){
return true;
}
node = node.next;
}
return false;
}
size() {
return this._length;
}
}
const AmazingRace = new LinkedList();
AmazingRace.add("Colombo, Sri Lanka");
AmazingRace.add("Lagos, Nigeria");
AmazingRace.add("Surat, India");
AmazingRace.add("Suzhou, China");
//Kent's check
AmazingRace.contains('Suzhou, China'); //true
AmazingRace.contains('Hanoi, Vietnam'); //false
AmazingRace.add('Hanoi, Vietnam');
AmazingRace.contains('Seattle, Washington'); //false
AmazingRace.add('Seattle, Washington');
AmazingRace.contains('North Pole'); // false
AmazingRace.add('North Pole');
좋 습 니 다. 현재 Kent 는 중복 을 피하 기 위해 추가 하기 전에 존재 하 는 지 확인 할 수 있 습 니 다.
다른 한편, 당신 은 왜 추가 하기 전에 검 사 를 하지 않 고 중복 을 피 하 는 지 생각 할 수 있 습 니 다.링크 나 임의의 데이터 구 조 를 실현 할 때 이론 적 으로 원 하 는 기능 을 추가 할 수 있 습 니 다.
너 는 심지어 기 존의 데이터 구조 에서 원래 의 방법 을 바 꿀 수 있다.REPL 에서 다음 코드 를 사용 해 보 세 요.
Array.prototype.push = () => {
return 'cat';
}
let arr = [];
arr.push('eggs'); // returns 'cat';
우리 가 이런 일 을 하지 않 은 이 유 는 약속의 기준 때문이다.기본적으로 개발 자 들 은 특정한 방법 이 어떻게 일 해 야 하 는 지 에 대해 기대 하고 있다.
비록 우리 의 링크 는 자 바스 크 립 트 의 네 이 티 브 라 이브 러 리 가 아니 지만, 우 리 는 그것 을 실현 할 때 더 많은 자 유 를 가지 고 있 지만, 이러한 데이터 구조 가 어떻게 작 동 하 는 지 우 리 는 여전히 기본 적 인 기 대 를 가지 고 있다.링크 자체 가 저장 하 는 값 이 유일 하 다 는 것 을 보장 하지 않 습 니 다.그러나 그들 은 확실히 contains 라 는 방법 을 제공 하여 우리 가 예비 검 사 를 할 수 있 도록 해 주 고 우리 목록 의 값 이 중복 되 지 않도록 유지 할 수 있 습 니 다.
Kent 는 그 가 수정 한 목록 을 다시 너 에 게 보 냈 지만, 그 중 일 부 는 문제 가 있 을 수 있다.예 를 들 어 북극 은 '과속 전진' 의 가장 좋 은 종점 이 아 닐 수도 있다.
그래서 일부 노드 를 제거 할 수 있 는 방법 을 만 들 기로 했 습 니 다.반드시 기억 해 야 할 것 은 한 노드 를 삭제 하면 목록 을 중단 하고 삭 제 된 노드 의 앞 뒤 두 노드 를 다시 연결 해 야 한 다 는 것 이다.
class Node {
constructor(value) {
this.value = value;
this.next = null;
}
}
class LinkedList {
constructor() {
this._head = null;
this._tail = null;
this._length = 0;
}
add(value) {
let node = new Node(value);
if(!this._head && !this._tail){
this._head = node;
this._tail = this._head;
}else{
this._tail.next = node;
this._tail = this._tail.next;
}
this._length++;
}
remove(value) {
if(this.contains(value)){ // see if our value exists
let current = this._head; // begin at start of list
let previous = this._head;
while(current){ // check each node
if(current.value === value){
if(this._head === current){ // if it's the head
this._head = this._head.next; // reset the head
this._length--; // update the length
return; // break out of the loop
}
if(this._tail === current){ // if it's the tail node
this._tail = previous; // make sure to reset it
}
previous.next = current.next; // unlink (see img below)
this._length--; // update the length
return; // break out of
}
previous = current; // look at the next node
current = current.next; // ^^
}
}
}
contains(value){
let node = this._head;
while(node){
if(node.value === value){
return true;
}
node = node.next;
}
return false;
}
size() {
return this._length;
}
}
const AmazingRace = new LinkedList();
AmazingRace.add("Colombo, Sri Lanka");
AmazingRace.add("Lagos, Nigeria");
AmazingRace.add("Surat, India");
AmazingRace.add("Suzhou, China");
AmazingRace.add('Hanoi, Vietnam');
AmazingRace.add('Seattle, Washington');
AmazingRace.add('North Pole');
//Kent's check
AmazingRace.remove('North Pole');
reove 방법의 코드 가 비교적 길다.본질 적 으로 그것 은 다음 과 같은 절차 에 따라 운행 한다.
1. 삭제 할 값 이 있 는 지 확인 합 니 다...
2. 목록 을 옮 겨 다 니 며 현재 노드 와 이전 노드 를 추적 해 야 합 니 다.
3. 그리고 현재 노드 가 삭제 할 점 이 라면 - >
4A 、 현재 노드 는 링크 의 머리 입 니 다.
4C 、 삭제 할 노드 가 아니라면 - > 계속 교체
방금 이 루어 진 reove 방법 이 있 습 니 다. 아래 줄 만 있 으 면 참가 자 들 이 얼 어 죽지 않 거나 새해 축 제 를 준비 하고 있 는 산 타 클로스 를 방해 하지 않 을 수 있 습 니 다.
AmazingRace.remove('North Pole');
자, 당신 은 이미 하나의 단일 체인 표 의 간단 한 실현 을 완성 하 였 습 니 다.원 소 를 추가 해서 목록 을 확장 할 수도 있 고, 원 소 를 제거 해서 목록 을 압축 할 수도 있다.
링크 의 첫 번 째 부분, 꼬리 부분 또는 임의의 노드 에 요 소 를 삽입 하고 싶다 면.너 는 스스로 이 방법 들 을 실현 해 야 한다.이 방법 들 의 이름과 매개 변 수 는 다음 과 같 아야 합 니 다.
addHead(value) {
}
insertAfter(target, value){
}
시간 복잡 도 분석
완전한 코드 를 다시 한 번 보 겠 습 니 다.
class LinkedList {
constructor() {
this._head = null;
this._tail = null;
this._length = 0;
}
add(value) {
let node = new Node(value);
if(!this._head && !this._tail){
this._head = node;
this._tail = this._head;
}else{
this._tail.next = node;
this._tail = this._tail.next;
}
this._length++;
}
remove(value) {
if(this.contains(value)){
let current = this._head;
let previous = this._head;
while(current){
if(current.value === value){
if(this._head === current){
this._head = this._head.next;
this._length--;
return;
}
if(this._tail === current){
this._tail = previous;
}
previous.next = current.next;
this._length--;
return;
}
previous = current;
current = current.next;
}
}
}
contains(value){
let node = this._head;
while(node){
if(node.value === value){
return true;
}
node = node.next;
}
return false;
}
size() {
return this._length;
}
// To Be Implemented
addHead(value) {
}
insertAfter(target, value){
}
Add 의 복잡 도 는 O (1) 입 니 다. tail 속성 추적 대기 열의 끝 이 있 기 때문에 전체 목록 을 옮 겨 다 닐 필요 가 없습니다.
Remove 의 복잡 도 는 O (n) 입 니 다. 최 악의 경우 전체 목록 을 옮 겨 다 녀 야 제거 해 야 할 노드 를 찾 을 수 있 습 니 다.비록 진정한 노드 제거 작업 은 O (1) 이지 만 (포인터 만 리 셋 하면 되 기 때문이다).
Contains 의 복잡 도 는 O (n) 입 니 다. 목록 에 지정 한 값 이 포함 되 어 있 는 지 확인 하기 위해 서 는 목록 전 체 를 옮 겨 다 녀 야 합 니 다.
addHead 의 복잡 도 는 O (1) 입 니 다. 우리 의 add 방법 과 비슷 합 니 다. 우 리 는 항상 목록 의 머리 를 알 기 때문에 옮 겨 다 닐 필요 가 없습니다.
insert After 의 복잡 도 는 O (n) 입 니 다. 위 에서 논의 한 Remove 방법 과 마찬가지 로 전체 목록 을 옮 겨 다 니 며 삽입 할 위 치 를 찾 아야 합 니 다.마찬가지 로 실제 삽입 작업 의 복잡 도 는 O (1) 이다.
링크 VS 배열
왜 배열 이 아 닌 링크 를 사용 합 니까?기술적 으로 배열 은 추가, 삽입, 삭제 등 모든 링크 작업 을 실행 할 수 있다.이 밖 에 자 바스 크 립 트 의 배열 은 이미 이러한 방법 을 갖 추고 있다.
가장 큰 차 이 는 삽입 과 삭제 에서 나온다.배열 은 색인 을 기반 으로 하기 때문에 배열 의 중간 에 요 소 를 삽입 하거나 삭제 할 때 그 뒤의 모든 요 소 를 새로운 색인 위치 로 초기 화 해 야 합 니 다.
100, 000 개의 요소 가 있 는 머리 나 중간 에 요 소 를 삽입 하 는 것 을 상상 해 보 세 요!이와 같은 삽입 과 삭제 작업 은 자원 을 매우 소모 한다.이 때문에 링크 는 자주 이동 하 는 대형 데이터 세트 에 사용 된다.
다른 한편, 배열 은 색인 에 기반 한 것 이기 때문에 찾기 에 매우 뛰어나다.요소 의 위 치 를 알 고 있다 면 array [position] 를 통 해 O (1) 시간 내 에 이 요 소 를 찾 을 수 있 습 니 다.
링크 는 보통 목록 을 순서대로 옮 겨 다 녀 야 합 니 다.이 때문에 배열 은 작은 데이터 세트 나 자주 이동 하지 않 는 데이터 세트 에 자주 사용 된다.
마디
링크:
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
