Verknüpfte Liste mit JavaScript-Datenstruktur und -Algorithmus_Grundkenntnisse

Einführung in verknüpfte Listen

Verknüpfte Listen sind eine gängige Datenstruktur und auch eine lineare Liste, sie speichert Daten jedoch nicht in linearer Reihenfolge. Stattdessen wird in jedem Knoten der Zeiger auf den nächsten Knoten gespeichert. Sie können es verstehen, wenn Sie sich das Bild ansehen. (Für diejenigen mit C-Hintergrundkenntnissen ist es möglicherweise einfacher, es zu verstehen.)
Durch die Verwendung einer verknüpften Listenstruktur kann der Nachteil eines Arrays behoben werden, bei dem die Datengröße im Voraus bekannt sein muss (ein Array in der C-Sprache erfordert eine vordefinierte Länge). Die verknüpfte Listenstruktur kann den Speicherplatz des Computers voll ausnutzen und erreichen flexible dynamische Speicherverwaltung.
Als nächstes stellen wir zwei gängige verknüpfte Listen vor: eine einseitig verknüpfte Liste und die Implementierung einer doppelt verknüpften Liste in JavaScript.

Einseitig verknüpfte Liste

Die einfachste Form einer verknüpften Liste ist eine einseitig verknüpfte Liste. Die Knoten in der verknüpften Liste enthalten zwei Teile. Der erste Teil speichert seine eigenen Informationen und der zweite Teil speichert einen Zeiger auf den nächsten Knoten. Der letzte Knoten zeigt auf NULL:

Implementierung einer einseitig verknüpften Liste in JavaScipt

Erstellen Sie zunächst einen Konstruktor.

/**
 * 单向链表构造函数
 */
function LinkedList() {
 /**
  * 单向链表中节点的构造函数
  * @param {Any} element 要传入链表的节点
  */
 var Node = function(element) {
  this.element = element;
  //下个节点的地址
  this.next = null;
 }

 //单向链表的长度
 var length = 0;
 //单向链表的头结点，初始化为NULL
 var head = null;
}

Es ist nicht schwer zu erkennen, dass der Konstruktor für einseitig verknüpfte Listen viel komplizierter ist als Stapel und Warteschlangen.
Eine einseitig verknüpfte Liste erfordert die folgenden Methoden:

1. append(element): Element am Ende der verknüpften Liste hinzufügen
2. insert(position,element): Fügt ein Element an einer bestimmten Position in der einseitig verknüpften Liste ein
3. indexOf(element): Finden Sie die Position eines Elements in einer einseitig verknüpften Liste
4. remove(element): Entferne das angegebene Element
5. removeAt(position): Entferne ein Element an einer bestimmten Position in der einseitig verknüpften Liste
6. getHead(): Den Kopf der einseitig verknüpften Liste abrufen
7. isAmpty(): Prüft, ob die einseitig verknüpfte Liste leer ist, gibt true zurück, wenn sie leer ist
8. toString(): Gibt den gesamten Inhalt der verknüpften Liste als String
aus
9. size(): Gibt die Länge der einseitig verknüpften Liste zurück
   

Anhängemethode:

Beschreibung: Elemente am Ende der einseitig verknüpften Liste hinzufügen.
Umsetzung:

/**
 * 向单向链表尾部添加元素
 * @param {Any} element 要加入链表的节点
 */
this.append = function(element) {
 var node = new Node(element);
 var current;

 if (head == null) {
  head = node;
 } else {
  // 当前项等于链表头部元素.
  // while循环到最后一个，从而将该节点加入链表尾部。
  current = head;
  // 当next为null时，判定为false。退出循环。
  while (current.next) {
   current = current.next;
  }
  current.next = node;
 }
 length++;
};

Methode einfügen:

Beschreibung: Fügen Sie ein Element an einer bestimmten Position in der einseitig verknüpften Liste ein.
Umsetzung:

/**
 * 向单向链表中插入某个元素
 * @param {Number} position 要插入的位置
 * @param {Any} element 要插入的元素
 * @return {Boolean}     插入成功返回true，失败返回false
 */
this.insert = function(position, element) {
 if (position >= 0 && position <= length) {
  var node = new Node(element);
  var current = head;
  var previous;
  var index = 0;

  if (position == 0) {
   node.next = current;
   head = node;
  } else {
   while (index++ < position) {
    previous = current;
    current = current.next;
   }

   previous.next = node;
   node.next = current;
  }

  length++;
  return true;
 } else {
  return false;
 }
};

indexOf-Methode:

Beschreibung: Finden Sie die Position eines Elements in einer einseitig verknüpften Liste.
Umsetzung:

/**
 * 寻找某个元素在单向链表中的位置
 * @param {Any} element 要寻找的元素
 * @return {Number}     返回值>=0则代表找到相应位置
 */
this.indexOf = function(element) {
 var current = head;
 var index = -1;

 while (current) {
  if (element === current.element) {
   return index;
  }
  index++;
  current = current.next;
 }

 return -1;
};

Methode entfernen:

Beschreibung: Das angegebene Element entfernen.
Umsetzung:

/**
 * 移除给定的元素
 * @param {Any} element 要移除的元素
 * @return {Number}     返回值>=0表示移除成功
 */
this.remove = function(element) {
 var index = this.indexOf(element);
 return this.removeAt(index);
};

removeAt-Methode:

Beschreibung: Entfernen Sie ein Element an einer bestimmten Position in der unidirektional verknüpften Liste.
Umsetzung:

/**
 * 移除单向链表中某一个元素
 * @param {Number} position 要移除元素的位置
 * @return {Any}     移除成功返回被移除的元素，不成功则返回NULL
 */
this.removeAt = function(position) {
 if (position > -1 && position < length) {
  var current = head;
  var previous;
  var index = 0;

  if (position == 0) {
   // 因为之前head指向第一个元素，现在把head修改为指向第二个元素。
   // 核心概念在于链表前后全靠指针链接，而非数组一般。
   // 所以只需要改变head的元素。
   head = current.next;
  } else {
   while (index++ < position) {
    // previous指要操作元素位置之前的那个元素，current表示之后的那个元素。
    previous = current;
    current = current.next;
   }

   previous.next = current.next;
  }

  length--;

  return current.element;
 } else {
  return null;
 }
};

getHead-Methode:

Beschreibung: Holen Sie sich den Kopf der einseitig verknüpften Liste.
Umsetzung:

/**
 * 获取单向链表的头部
 * @return {Any} 单向链表的头部
 */
this.getHead = function() {
 return head;
}

isAmpty, toString, Größenmethoden

Implementierung:

/**
 * 判断单向链表是否为空
 * @return {Boolean} 为空则返回true，不为空则返回false
 */
this.isAmpty = function() {
 return length === 0
};

/**
 * 将链表所有内容以字符串输出
 * @return {String} 要输出的字符串
 */
this.toString = function() {
 var current = head;
 var string = '';

 while (current) {
  string += current.element;
  current = current.next;
 }
 return string;
};

/**
 * 返回单向链表长度
 * @return {Number} 单向链表的长度
 */
this.size = function() {
 return length;
};

Doppelt verknüpfte Liste

Doppelt verknüpfte Listen sind einfach verknüpften Listen sehr ähnlich. In einer einseitig verknüpften Liste gibt es nur einen Link zum nächsten Knoten. In einer doppelt verknüpften Liste gibt es jedoch einen Link zum vorherigen Knoten, der bidirektional ist.

Implementierung einer doppelt verknüpften Liste in JavaScipt

Erstens ist es immer noch der Konstruktor:

/**
 * 双向链表的构造函数
 */
function DoublyLinkedList() {
 /**
  * 双向链表中节点的构造函数
  * @param {Any} element 要传入链表的元素
  */
 var Node = function(element) {
  this.element = element;
  this.prev = null;
  this.next = null;
 }

 //双向链表的长度
 var length = 0;
 //双向链表的头结点，初始化为NULL
 var head = null;
 //双向链表的尾结点，初始化为NULL
 var tail = null;
}

Doppelt verknüpfte Listen benötigen die folgenden Methoden:

1. append(element): Elemente am Ende der doppelt verknüpften Liste hinzufügen
2. insert(position,element): Fügt ein Element an einer bestimmten Position in der doppelt verknüpften Liste ein
3. removeAt(position): Entferne ein Element an einer bestimmten Position in der doppelt verknüpften Liste
4. showHead(): Den Kopf der doppelt verknüpften Liste abrufen
5. showLength(): Ermittelt die Länge der doppelt verknüpften Liste
6. showTail(): Holen Sie sich das Ende der doppelt verknüpften Liste
   

Anhängemethode:

Beschreibung: Elemente am Ende der doppelt verknüpften Liste hinzufügen
Umsetzung:

/**
 * 向链表尾部添加元素
 * @param {Any} element 要加入链表的节点
 * @return {Any}     加入链表的节点
 */
this.append = function(element) {
 var node = new Node(element);

 if (head === null) {
  head = node;
  tail = node;
 } else {
  var previous;
  var current = head;

  while (current.next) {
   current = current.next;
  }

  current.next = node;
  node.prev = current;
  tail = node;
 }

 length++;
 return node;
};

Methode einfügen:

Beschreibung: Fügen Sie ein Element an einer bestimmten Position in der doppelt verknüpften Liste ein.
Umsetzung:

/**
 * 向链表中插入某个元素
 * @param {Number} position 要插入的位置
 * @return {Boolean}     插入成功返回true，失败返回false
 */
this.insert = function(position, element) {
 if (position >= 0 && position <= length) {

  var node = new Node(element);
  var index = 0;
  var previous;
  var current = head;

  if (position === 0) {

   if (head === null) {
    head = node;
    tail = node;
   } else {
    current.prev = node;
    node.next = current;
    head = node;
   }
  } else if (position === length) {

   current = tail;
   current.next = node;
   node.prev = current;
   tail = node;
  } else {

   while (index++ < position) {
    previous = current;
    current = current.next;
   }

   previous.next = node;
   node.prev = previous;
   current.prev = node;
   node.next = current;
  }

  length++;
  return true;
 } else {
  return false;
 }
};

removeAt-Methode:

Beschreibung: Entfernen Sie ein Element an einer bestimmten Position in der doppelt verknüpften Liste.
Umsetzung:

/**
 * 移除链表中某一个元素
 * @param {Number} position 要移除元素的位置
 * @return {Any}       移除成功返回被移除的元素，不成功则返回false
 */
this.removeAt = function(position) {
 if (position > -1 && position < length) {
  var current = head;
  var index = 0;
  var previous;

  if (position === 0) {
   head = current.next;

   if (length === 1) {
    tail = null;
    head.prev = null;
   }
  } else if (position === length - 1) {
   current = tail;
   tail = current.prev;
   tail.next = null;
  } else {
   while (index++ < position) {
    previous = current.prev;
    current = current.next;
   }
   previous.next = current.next;
   current.next.prev = previous;
  }

  length--;
  return current.element;
 } else {
  return false;
 }
};

showHead-, showLength-, showTail-Methoden

Implementierung:

/**
 * 获取链表的头部
 * @return {Any} 链表的头部
 */
this.showHead = function() {
 return head;
};

/**
 * 获取链表长度
 * @return {Number} 链表长度
 */
this.showLength = function() {
 return length;
};

/**
 * 获取链表尾部
 * @return {Any} 链表尾部
 */
this.showTail = function() {
 return tail;
};

Impressionen

In diesem Abschnitt zu verknüpften Listen wird grundsätzlich der gesamte Code zuerst entsprechend den Anforderungen geschrieben und dann nach dem Schreiben mit dem Buch verglichen. Es stellte sich heraus, dass er augenblicklich in Schutt und Asche gelegt wurde. In meinem eigenen Schreiben gibt es viele versteckte Schwachstellen, und die Logik ist auch sehr verwirrend. Es scheint, dass er noch zu jung ist.