数据结构与算法Javascript描述（四）双向链表

一时失言乱红尘 2022-08-21 02:13 197阅读 0赞

尽管从链表的头节点遍历到尾节点很简单，但反过来，从后向前遍历则没那么简单。通过给Node 对象增加一个属性，该属性存储指向前驱节点的链接，这样就容易多了。此时向链表插入一个节点需要更多的工作，我们需要指出该节点正确的前驱和后继。但是在从链表中删除节点时，效率提高了，不需要再查找待删除节点的前驱节点了。

<span style="white-space:pre">			</span>function Node(element) {
    				this.element = element;
    				this.next = null;
    				this.previous = null;
    			}
    			function BLList() {
    				this.head = new Node("head");
    				this.find = find;
    				this.insert = insert;
    				this.remove = remove;
    				this.display = display;
    				this.findLast = findLast;
    				this.dispReverse = dispReverse;
    			}
    			function find(elem) {
    				var current = this.head;
    				while(current!== null && current.element !== elem) {
    					current = current.next;
    				}
    				return current;
    			}

<span style="color:#ff6666;">  不明白为什么这里在插入时，没有current.next.previous = newNode;并且我加上这一句的话程序会报错。</span>
    			function insert(newElem,elem) {
    				var newNode = new Node(newElem),
    					current = this.find(elem);
    				newNode.next = current.next;
    				newNode.previous = current;
    				current.next = newNode;
    
    			}
    			function remove(elem) {
    				var curNode = this.find(elem);
    				if(curNode.next !== null) {
    					curNode.previous.next = curNode.next;
    					curNode.next.previous = curNode.previous;
    					
    				}else {
    					curNode.previous.next = null;
    				}
    				curNode.next = null;
    				curNode.previous = null;
    				
    			}
    			function display() {
    				var current = this.head;
    				while(current.next!==null) {
    					console.log(current.next.element);
    					current = current.next;
    				}
    			}
    			function findLast() {
    				var curNode = this.head;
    				while(curNode.next !== null) {
    					curNode = curNode.next;
    				}
    				return curNode;
    			}
    			function dispReverse() {
    				var curNode = this.findLast();
    				while(curNode.previous !== null) {
    					console.log(curNode.element);
    					curNode = curNode.previous;
    				}
    			}
    			var bllist = new BLList();
    			bllist.insert("z1","head");
    			bllist.insert("z2","z1");
    			bllist.insert("z3", "z2");
    			bllist.insert("z4", "z1");
    			bllist.display();