Structure de données JavaScript et liste liée à l'algorithme_Connaissances de base

Introduction aux listes chaînées

La liste chaînée est une structure de données courante et est également une liste linéaire, mais elle ne stocke pas les données dans un ordre linéaire. Au lieu de cela, dans chaque nœud, le pointeur vers le nœud suivant est stocké. Vous pouvez comprendre en regardant la photo. (Ceux qui ont une formation en langage C peuvent avoir plus de facilité à le comprendre).
L'utilisation d'une structure de liste chaînée peut surmonter l'inconvénient d'un tableau qui nécessite de connaître la taille des données à l'avance (un tableau en langage C nécessite une longueur prédéfinie. La structure de liste chaînée peut utiliser pleinement l'espace mémoire de l'ordinateur et atteindre). gestion flexible de la mémoire dynamique.
Ensuite, nous présenterons deux listes chaînées courantes : la liste chaînée unidirectionnelle et l'implémentation de la liste chaînée double en JavaScript.

Liste chaînée à sens unique

La forme la plus simple d'une liste chaînée est une liste chaînée unidirectionnelle. Les nœuds de la liste chaînée contiennent deux parties. La première partie stocke ses propres informations et la seconde partie stocke un pointeur vers le nœud suivant. Le dernier nœud pointe vers NULL :

Implémentation d'une liste chaînée unidirectionnelle dans JavaScipt

Tout d’abord, créez un constructeur.

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

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

Il n'est pas difficile de voir que le constructeur de liste chaînée unidirectionnelle est beaucoup plus compliqué que les piles et les files d'attente.
Une liste chaînée unidirectionnelle nécessite les méthodes suivantes :

1. append(element) : Ajouter un élément à la fin de la liste chaînée
2. insert(position,element) : Insère un élément dans une certaine position dans la liste chaînée unidirectionnelle
3. indexOf(element) : Rechercher la position d'un élément dans une liste chaînée unidirectionnelle
4. remove(element) : Supprime l'élément donné
5. removeAt(position) : Supprime un élément à une certaine position dans la liste chaînée unidirectionnelle
6. getHead() : Obtenez la tête de la liste chaînée à sens unique
7. isAmpty() : vérifie si la liste chaînée unidirectionnelle est vide, renvoie vrai si elle est vide
8. toString() : affiche tout le contenu de la liste chaînée sous forme de chaîne
9. size() : renvoie la longueur de la liste chaînée unidirectionnelle
   

méthode d'ajout :

Description : Ajoutez des éléments à la fin de la liste chaînée unidirectionnelle.
Mise en œuvre :

/**
 * 向单向链表尾部添加元素
 * @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++;
};

méthode d'insertion :

Description : Insérez un élément dans une certaine position dans la liste chaînée unidirectionnelle.
Mise en œuvre :

/**
 * 向单向链表中插入某个元素
 * @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;
 }
};

Méthode indexOf :

Description : Recherchez la position d'un élément dans une liste chaînée unidirectionnelle.
Mise en œuvre :

/**
 * 寻找某个元素在单向链表中的位置
 * @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;
};

méthode de suppression :

Description : Supprime l'élément donné.
Mise en œuvre :

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

Méthode RemoveAt :

Description : Supprimez un élément à une certaine position dans la liste chaînée unidirectionnelle.
Mise en œuvre :

/**
 * 移除单向链表中某一个元素
 * @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;
 }
};

Méthode getHead :

Description : Obtenez la tête de la liste de liens à sens unique.
Mise en œuvre :

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

isAmpty, toString, méthodes de taille

Mise en œuvre :

/**
 * 判断单向链表是否为空
 * @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;
};

Liste chaînée double

Les listes doublement chaînées sont très similaires aux listes chaînées unidirectionnelles. Dans une liste chaînée unidirectionnelle, il n’y a qu’un lien vers le nœud suivant. Mais dans une liste doublement chaînée, il existe un lien vers le nœud précédent, qui est bidirectionnel.

Implémentation de liste doublement chaînée dans JavaScipt

D’abord, c’est toujours le constructeur :

/**
 * 双向链表的构造函数
 */
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;
}

Les listes doublement chaînées nécessitent les méthodes suivantes :

1. append(element) : Ajouter des éléments à la fin de la liste doublement chaînée
2. insert(position,element) : Insérer un élément dans une certaine position dans la liste doublement chaînée
3. removeAt(position) : Supprime un élément à une certaine position dans la liste doublement chaînée
4. showHead() : Obtenez la tête de la liste doublement chaînée
5. showLength() : Obtenez la longueur de la liste doublement chaînée
6. showTail() : Obtenez la queue de la liste doublement chaînée
   

méthode d'ajout :

Description : Ajouter des éléments à la fin de la liste doublement chaînée
Mise en œuvre :

/**
 * 向链表尾部添加元素
 * @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;
};

méthode d'insertion :

Description : Insérez un élément à une certaine position dans la liste doublement chaînée.
Mise en œuvre :

/**
 * 向链表中插入某个元素
 * @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;
 }
};

Méthode RemoveAt :

Description : Supprime un élément à une certaine position dans la liste doublement chaînée.
Mise en œuvre :

/**
 * 移除链表中某一个元素
 * @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;
 }
};

Méthodes showHead, showLength, showTail

Mise en œuvre :

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

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

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

Impressions

Dans cette section sur les listes chaînées, essentiellement tout le code est d'abord écrit selon les exigences, puis comparé au livre après l'écriture. On a constaté qu’il avait été réduit à l’état d’ordure en un instant. Il y a de nombreuses lacunes cachées dans mes propres écrits, et la logique est également très déroutante. Il semble qu'il soit encore trop jeune.