JavaScript 데이터 구조(그림 및 텍스트)의 연결 목록 구현 방법 소개-JS 튜토리얼-php.cn

연결된 목록은 일반적인 데이터 구조입니다. 스토리지를 동적으로 할당하는 구조입니다. 이번 글에서는 참고할만한 좋은 JavaScript 데이터 구조에서의 연결 리스트 구현을 주로 소개합니다. 아래 에디터로 살펴보겠습니다

이전 포스터에서는 각각 데이터 구조 스택과 큐의 구현에 대해 논의했습니다. 당시 사용된 데이터 구조는 모두 배열을 사용하여 구현되었지만 때로는 배열이 가장 많지 않습니다. 최적의 데이터 구조입니다. 예를 들어 배열의 요소를 추가하고 삭제할 때 다른 요소를 이동해야 하며 JavaScript의 spit() 메서드를 사용하면 다른 요소에 액세스할 필요가 없습니다. 배열을 사용할 때 속도가 느리다면 연결 목록을 사용해 보세요.

링크드 리스트의 개념

링크드 리스트는 일반적인 데이터 구조입니다. 스토리지를 동적으로 할당하는 구조입니다. 연결된 목록에는 요소를 가리키는 주소를 저장하는 head로 표시되는 "헤드 포인터" 변수가 있습니다. 각 노드는 객체의 참조를 사용하여 다른 노드를 가리키는 참조를 체인이라고 합니다.

배열 요소는 아래 첨자(위치)로 참조되는 반면, 연결 목록 요소는 관계로 참조됩니다. 따라서 연결리스트의 삽입 효율성은 매우 높다. 다음 그림은 연결리스트 노드 d의 삽입 과정을 보여준다:

삭제 과정:

객체 기반 연결 목록

Node 클래스와 LinkedList 클래스라는 두 개의 클래스를 정의합니다. Node는 노드 데이터이고 LinkedList는 해당 메서드를 저장합니다. 연결리스트를 운영합니다.

먼저 Node 클래스를 살펴보세요.

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

로그인 후 복사

요소는 노드에 데이터를 저장하는 데 사용되고, next는 아래 노드를 가리키는 링크를 저장하는 데 사용됩니다.

LinkedList 클래스:

function LinkedList(){
     this.head = new Node(&#39;head&#39;);
     this.find = find;
     this.insert = insert;
     this.remove = remove;
     this.show = show;
}

로그인 후 복사

find() 메서드, 헤드 노드에서 시작하여 항목 콘텐츠와 동일한 요소가 발견될 때까지 연결된 목록 노드를 따라 검색한 다음 노드가 반환됩니다. 찾을 수 없으면 비어 있는 상태를 반환합니다.

아아아

삽입 방법. 이전 요소 삽입 시연에서 볼 수 있듯이 삽입을 구현하는 간단한 네 단계가 있습니다.

1. 노드 생성

2. 대상 노드 찾기

3. 대상 노드를 수정합니다. 포인트의 다음 지점이 링크를 가리킵니다

4. 대상 노드의 다음 값을 해당 노드의 다음

function find(item){
     var currentNode = this.head;//从头结点开始
     while(currentNode.element!=item){
         currentNode = currentNode.next;
     }
     return currentNode;//找到返回结点数据，没找到返回null
}

로그인 후 복사

Remove() 메서드에 할당합니다. 삽입됩니다. 노드를 삭제하려면 먼저 삭제된 노드의 이전 노드를 찾아야 합니다. 이러한 이유로 frontNode() 메서드를 정의합니다.

function insert(newElement,item){
     var newNode = new Node(newElement);
     var currentNode = this.find(item);
     newNode.next = currentNode.next;
     currentNode.next = newNode;
 }

로그인 후 복사

간단한 세 단계:

1. node

2. 대상 노드의 이전 노드를 찾습니다

3. 삭제된 노드 뒤의 노드 n을 가리키도록 이전 노드의 다음 노드를 수정합니다

function frontNode(item){
     var currentNode = this.head;
     while(currentNode.next.element!=item&&currentNode.next!=null){
         currentNode = currentNode.next;
     }   
     return currentNode;
}

로그인 후 복사

Show() 메소드 :

function remove(item){
     var frontNode = this.frontNode(item);
     //console.log(frontNode.element);
     frontNode.next = frontNode.next.next;
 }

로그인 후 복사

테스트 프로그램:

function show(){
     var currentNode = this.head,result;
     while(currentNode.next!=null){
         result += currentNode.next.element;//为了不显示head结点
         currentNode = currentNode.next;
     }
}

로그인 후 복사

출력:

이중 연결 목록

From 연결 리스트를 헤드 노드에서 테일 노드로 순회하는 것은 매우 간단하지만 때로는 뒤에서 앞으로 순회해야 하는 경우도 있습니다. 이 시점에서 이전 노드에 대한 링크를 저장하는 노드 객체에 속성 을 추가할 수 있습니다. 포스터는 다음 다이어그램을 사용하여 이중 연결 목록의 작동 원리를 설명합니다.

먼저 Node 클래스에 전면 속성을 추가합니다:

var list = new LinkedList();
list.insert("a","head");
list.insert("b","a");
list.insert("c","b");
console.log(list.show());
list.remove("b");
console.log(list.show());

로그인 후 복사

물론 해당 insert() 메서드도 수행하고 제거( ) 그에 따른 메소드 수정:

function Node(element){
  this.element = element;
  this.next = null;
   this.front = null;
 }

로그인 후 복사

연결 리스트를 역순으로 표시:

마지막 노드를 찾으려면 이중 연결 리스트에 메소드를 추가해야 합니다. findLast() 메소드는 연결된 목록에서 마지막 노드를 찾으므로 체인을 앞에서 뒤로 이동할 필요가 없습니다.

function insert(newElement,item){
  var newNode = new Node(newElement);
  var currentNode = this.find(item);
  newNode.next = currentNode.next;
  newNode.front = currentNode;//增加front指向前驱结点
  currentNode.next = newNode;
}
function remove(item){  
  var currentNode = this.find(item);//找到需要删除的节点
  if (currentNode.next != null) {
    currentNode.front.next = currentNode.next;//让前驱节点指向需要删除的节点的下一个节点
    currentNode.next.front = currentNode.front;//让后继节点指向需要删除的节点的上一个节点
    currentNode.next = null;//并设置前驱与后继的指向为空
    currentNode.front = null;    
  }  
}

로그인 후 복사

역방향 출력 구현:

function findLast() {//查找链表的最后一个节点
  var currentNode = this.head;
  while (currentNode.next != null) {
    currentNode = currentNode.next;
  }
  return currentNode;
}

로그인 후 복사

테스트 프로그램:

function showReverse() {
  var currentNode = this.head, result = "";
  currentNode = this.findLast(); 
  while(currentNode.front!=null){
    result += currentNode.element + " ";
    currentNode = currentNode.front;
  }
  return result;
}

로그인 후 복사

출력:

루프 Linked list

순환 연결 리스트는 연결 저장소 구조의 또 다른 형태입니다. 그 특징은 리스트의 마지막 노드의 포인터 필드가 헤드 노드를 가리키며 전체 연결 리스트가 링을 형성한다는 것입니다. 순환 연결 목록은 단일 연결 목록과 유사하며 노드 유형은 동일합니다. 유일한 차이점은 순환 연결 목록을 생성할 때 헤드 노드의 다음 속성이 자신을 가리키도록 한다는 것입니다. 즉,

head.next = head

이 동작은 모든 요소에 전송됩니다. 연결된 목록 노드에서 각 노드의 다음 속성은 연결된 목록의 헤드 노드를 가리킵니다. 포스터는 다음 그림을 사용하여 원형 연결 목록을 나타냅니다.

구성 방법 수정:

function LinkedList(){
  this.head = new Node(&#39;head&#39;);//初始化
  this.head.next = this.head;//直接将头节点的next指向头节点形成循环链表
  this.find = find;
  this.frontNode = frontNode;
  this.insert = insert;
  this.remove = remove;
  this.show = show; 
}

로그인 후 복사

这时需要注意链表的输出方法show()与find()方法，原来的方式在循环链表里会陷入死循环，while循环的循环条件需要修改为当循环到头节点时退出循环。

function find(item){
  var currentNode = this.head;//从头结点开始
  while(currentNode.element!=item&&currentNode.next.element!=&#39;head&#39;){
    currentNode = currentNode.next;
  }
  return currentNode;//找到返回结点数据，没找到返回null
}
function show(){
  var currentNode = this.head,result = "";
  while (currentNode.next != null && currentNode.next.element != "head") {   
    result += currentNode.next.element + " ";
    currentNode = currentNode.next;
  }
  return result;
}

로그인 후 복사

测试程序：

var list = new LinkedList();
list.insert("a","head");
list.insert("b","a");
list.insert("c","b");
console.log(list.show());
list.remove("b");
console.log(list.show());

로그인 후 복사

测试结果：