数据结构与算法Javascript描述（三）链表

清疚 2022-08-21 02:13 221阅读 0赞

数组不总是组织数据的最佳数据结构，因为数组的长度是固定的，所以当数组已被数据填满时，要再加入新的元素就会非常困难。在数组中，添加和删除元素也很麻烦，因为需要将数组中的其他元素向前或向后平移，以反映数组刚刚进行了添加和删除操作。然而，JavaScript 的数组并不存在上述问题，因为使用split() 方法不需要再访问数组中的其他元素了。JavaScript中的数组的主要问题是，它们被实现成了对象，与其他语言相比，效率很低。如果你发现数组在实际使用时很慢，就可以考虑使用链表来替代它。除了对数据的随机访问，链表几乎可以用在任何可以使用一维数组的情况中。如果需要随机访问，数组仍然是更好的选择。

链表中插入节点的效率很高，删除节点也很简单。链表还有其他操作，但插入和删除元素最能说明链表为什么如此有用。

链表包括两个类。Node 类用来表示节点，LinkedList类提供了插入节点、删除节点、显示列表元素的方法，以及其他一些辅助方法。

<span style="white-space:pre">			</span>function Node(element) {
    				this.element = element;
    				this.next = null;
    			}
    			function LList() {
    				this.head = new Node("head");
    				this.find = find;
    				this.insert = insert;
    				this.remove = remove;
    				this.display = display;
    				this.findPrevious = findPrevious;
    
    				function find(elem) {
    					var curNode = this.head;
    					while(curNode.element !== elem&&curNode!==null) {
    						curNode = curNode.next;
    					}
    					return curNode;
    				}
    				function insert(newElem, item) {
    					var node = new Node(newElem),
    						current = this.find(item);
    					node.next = current.next;
    					current.next = node;
    				}
    				function findPrevious(elem) {
    					var curNode = this.head;
    					while((curNode.next!==null)&&(curNode.next.element !== elem)) {
    						curNode = curNode.next;
    					}
    					return curNode;
    				}
    				function remove(elem) {
    					var preNode = this.findPrevious(elem);
    					if(preNode.next!==null) {
    						preNode.next = preNode.next.next;
    					}
    				}
    				function display() {
    					var curNode = this.head;
    					while(curNode.next!==null) {
    						console.log(curNode.next.element);
    						curNode = curNode.next;
    					}
    				}
    			}
    			var cities = new LList();
    			cities.insert("Conway", "head");
    			cities.insert("Russellville", "Conway");
    			cities.insert("Carlisle", "Russellville");
    			cities.insert("Alma", "Carlisle");
    			cities.remove("Alma");