1.数组的缺点 数组不总是组织数据的最佳数据结构，原因如下。 在很多编程语言中，数组的长度是固定的，所以当数组已被数据填满时，再要加入新的元素就会非常困难。 在数组中，添加和删除元素也很麻烦，因为需要将数组中的其他元素向前或向后平移，以反映数组刚刚进行了添加或删除操作。 然而，JavaScript 的数组并不存在上述问题，因为使用splice() 方法不需要再访问数组中的其他元素了。 JavaScript 中数组的主要问题是，它们被实现成了对象，与其他语言（比如C++ 和Java）的数组相比，效率很低 如果你发现数组在实际使用时很慢，就可以考虑使用链表来替代它。除了对数据的随机访问，链表几乎可以用在任何可以使用一维数组的情况中。 如果需要随机访问，数组仍然是更好的选择。 2.定义链表 链表是由一组节点组成的集合。每个节点都使用一个对象的引用指向它的后继。指向另一个节点的引用叫做链。 数组元素靠它们的位置进行引用，链表元素则是靠相互之间的关系进行引用。 链表中插入一个节点的效率很高。 向链表中插入一个节点，需要修改它前面的节点（前驱），使其指向新加入的节点，而新加入的节点则指向原来前驱指向的节点。 从链表中删除一个元素也很简单。 将待删除元素的前驱节点指向待删除元素的后继节点， 同时将待删除元素指向null，元素就删除成功了。链表还有其他一些操作，但插入和删除元素最能说明链表为什么如此有用。 3.设计一个基于对象的链表 我们设计的链表包含两个类。 Node 类用来表示节点，LinkedList 类提供了插入节点、删除节点、显示列表元素的方法，以及其他一些辅助方法。 Node类： LinkedList类： 插入新节点： insert，该方法向链表中插入一个节点。向链表中插入新节点时，需要明确指出要在哪个节点前面或后面插入。 如何在一个已知节点后面插入元素： 在一个已知节点后面插入元素时，先要找到“后面”的节点。为此，创建一个辅助方法find()，该方法遍历链表，查找给定数据。如果找到数据，该方法就返回保存该数据的节点。 find() 方法演示了如何在链表上进行移动。首先，创建一个新节点，并将链表的头节点赋给这个新创建的节点。 然后在链表上进行循环，如果当前节点的element 属性和我们要找的信息不符，就从当前节点移动到下一个节点。 如果查找成功，该方法返回包含该数据的节点；否则，返回null。 从链表中删除一个节点： 从链表中删除节点时，需要先找到待删除节点前面的节点。找到这个节点后，修改它的next 属性，使其不再指向待删除节点，而是指向待删除节点的下一个节点。 代码实现：
<script type="text/javascript">/*** Node类：* element 用来保存节点上的数据* next 用来保存指向下一个节点的链接*/function Node(element){this.element = element;this.next = null;}/*** LinkedList类* LList 类提供了对链表进行操作的方法。* 包括插入删除节点、在列表中查找给定的值。* 链表只有一个属性，那就是使用一个Node 对象来保存该链表的头节点。** head 节点的next 属性被初始化为null* 当有新元素插入时，next 会指向新的元素,所以在这里我们没有修改next 的值。*/function LList(){this.head = new Node("head");this.find = find;this.insert = insert;this.remove = remove;this.display = display;this.findPrevious = findPrevious;}/*** 遍历链表，查找给定数据。* 如果找到数据，该方法就返回保存该数据的节点*/function find(item){var currNode = this.head;while(currNode.element != item){currNode = currNode.next;}return currNode;}/** 插入新节点* 在item元素（已知节点）后面插入newElement*/function insert(newElement, item){var newNode = new Node(newElement);var current = this.find(item);newNode.next = current.next;current.next = newNode;}/*** 查找待删除元素的上一个节点* 该方法遍历链表中的元素，检查每一个节点的下一个节点中是否存储着待删除数据。* 如果找到，返回该节点（即“前一个”节点）*/function findPrevious(item){var currNode = this.head;while(currNode.next!=null && currNode.next.element != item){currNode = currNode.next;}return currNode;}/*** 从链表中删除节点* 需要先找到待删除节点前面的节点。* 找到这个节点后，修改它的next 属性，使其不再指向待删除节点，而是指向待删除节点的下一个节点。*/function remove(item){var prevNode = this.findPrevious(item);if(prevNode.next != null){prevNode.next = prevNode.next.next;}}/** 显示链表中的元素*/function display(){var currNode = this.head;while(currNode.next != null){console.log(currNode.next.element);currNode = currNode.next;}}//测试代码var cities = new LList();cities.insert("Conway", "head");cities.insert("Russellville", "Conway");cities.insert("Carlisle", "Russellville");cities.insert("Alma", "Carlisle");cities.display();cities.remove("Carlisle");cities.display();</script>
打印：
如果觉得《数据结构与算法JavaScript描述——链表》对你有帮助，请点赞、收藏，并留下你的观点哦！
