JavaScript-Tutorial – Implementierung der Datenstruktur verknüpfter Listen

Verknüpfte Liste ist eine übliche Basisdatenstruktur, aber sie speichert Daten nicht in linearer Reihenfolge, sondern speichert einen Zeiger auf den nächsten Knoten. Im Folgenden verwenden wir JavaScript-Code, um die Datenstruktur der verknüpften Liste zu implementieren.

Die verknüpfte Liste ist eine allgemeine Grunddatenstruktur, eine lineare Liste, speichert jedoch keine Daten in linearer Reihenfolge. Es handelt sich um einen Zeiger (. In jedem Knoten gespeicherter Zeiger zum nächsten Knoten - Wikipedia

Das Obige ist Wikipedias Interpretation der verknüpften Liste. Im Folgenden verwenden wir JavaScript-Code, um die Datenstruktur der verknüpften Liste zu implementieren

Implementieren Sie die Node-Klasse, um den Knoten darzustellen

/**
 * Node 类用来表示节点
 * element 用来保存节点上的数据
 * next 用来保存指向下一个节点的链接
 */
function Node(element) {
 this.element = element;
 this.next = null;
}
LList类提供对链表操作的方法
/**
 * LList 类提供了对链表进行操作的方法
 * 链表只有一个属性，
 * 使用一个 Node 对象来保存该链表的头节点。
 */
class LList {
 constructor() {
  this.head = new Node('head');
 }
 // 查找节点
 find(item) {
  let currNode = this.head;
  while(currNode.element !== item) {
   currNode = currNode.next;
  }
  return currNode;
 }
 // 查找前一个节点
 findPre(item) {
  if(item === 'head') throw new Error('now is head!');
  let currNode = this.head;
  while (currNode.next && currNode.next.element !== item) {
   currNode = currNode.next;
  }
  return currNode;
 }
 // 插入新节点
 insert(newElement, item) {
  let newNode = new Node(newElement);
  let currNode = this.find(item);
  newNode.next = currNode.next;
  currNode.next = newNode;
 }
 // 删除一个节点
 remove(item) {
  let preNode = this.findPre(item);
  if(preNode.next !== null) {
   preNode.next = preNode.next.next;
  }
 }
 // 显示链表中的元素
 display() {
  let currNode = this.head;
  while(currNode.next !== null) {
   console.log(currNode.next.element);
   currNode = currNode.next;
  }
 }
}

Testcode

const list = new LList(); 
// LList { head: Node { element: 'head', next: null } }
list.insert('0', 'head');
list.insert('1', '0');
list.insert('2', '1');
list.insert('3', '2');
list.remove('1');
console.log(list); 
// LList { head: Node { element: 'head', next: Node { element: '0', next: [Object] } } }
console.log(list.display()); // 0 2 3
console.log(list.findPre('1')); 
// Node { element: '0', next: Node { element: '1', next: Node { element: '2', next: [Object] } } }

Das Obige ist eine einfache Implementierung der Datenstruktur einer einfachen verknüpften Liste mit JavaScript: smile:

Das obige ist der detaillierte Inhalt vonJavaScript-Tutorial – Implementierung der Datenstruktur verknüpfter Listen. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!