链表 - javascript

简介

链表：（链式存储，线性表）元素不之间连续，通过指针将一组零散的内存块串联起来；像火车的车厢一样，通过挂钩将车厢串联起来：如（图1）所示

（图1）所示一目了然，（图1）是一个单向链表，就是对象中的next指针指向下一个对象；最终指向null；原型链的设计也是如此；
常见的链表有：

(图1)：

(图2)：

(图3)：

1. 单链：节点间单向，图1所示
2. 双链：除了首尾节点间双向，图2所示
3. 循环链：首位节点间双向，图3所示

   实现

4. 单向链表：

//节点创建
 function Node(element) {
        this.element = element
        this.next = null
    }
 //单向链表 
 class LinkedList {
		constructor() {
            this.length = 0;
            this.head = null;
        }
		//添加
        append(element) {
            let newNode = new Node(element);
            if (this.head == null) {
                this.head = newNode
            } else {
                let cruuent = this.head;
                while (cruuent.next) {
                    cruuent = cruuent.next
                }
                cruuent.next = newNode
            }
            this.length += 1
        }
        //查找
         find(item) {
            var curNode = this.head;
            while (curNode.element != item) {
                curNode = curNode.next;
            }
            return curNode
        }
		//插入
        insert(newElement, item) {
            var newNode = new Node(newElement);
            var current = this.find(item);
            newNode.next = current.next;
            newNode.previous = current;
            current.next = newNode
            this.length++
        }
		//查找前一个
        findPrevious(item) {
            var curNode = this.head;
            while (curNode.next && curNode.next.element != item) {
                curNode = curNode.next
            }
            return curNode
        }
		//移除
        singleRemove(item) {
            var prevNode = this.findPrevious(item);
            if (prevNode.next) {
                prevNode.next = prevNode.next.next
            }
        }
    }

2.双向链表

//双向链表除了头尾其他节点首尾相接；
   //创建双向链表节点
   function doubleNode(element) {
       this.element = element;
       this.next = null;
       this.previous = null
   }

 append(element) {
           let newNode = new doubleNode(element);
           if (!this.head) {
               this.head = newNode
           } else {
               let current = this.head
               while (current.next) {
                   current = current.next
               }
               current.next = newNode
               newNode.previous = current
           }
           this.length += 1
       }

  find(item) {
           let current = this.head;
           while (current && current.element != item) {
               current = current.next
           }
           return current
       }


       insert(newElement, item) {
           let current = this.find(item);
           let newNode = new doubleNode(newElement);
           current.next.previous = newNode;
           newNode.next = current.next
           newNode.previou = current;
           current.next = newNode;
           this.length += 1

       }

       singleRemove(item) {
           let current = this.find(item);
           if (current.next) {
               current.previous.next = current.next;
               current.previous.previous = current.previous;
               current.previous.next.previous = current.previous
               current.previous = null;
               current.next = null
           }

       }

3.双向链表

//双向链表的尾部指向头部

4.实现链表的反转

function myReverse(LinkedList) {
    let {
        head:current 
    } = LinkedList;
    let next = null;
    let pre = null;
    while (current != null) {
        next = current.next;
        current.next = pre;
        pre = current;
        current = next;
    }
    list.head = pre
}

6.测试

var list = new LinkedList()
  list.append(1)
  list.append(2)
  list.append(4)
  list.insert(2, 3)
  myReverse(list)
  console.log(list);

结束

基本知道是个什么东西就比较简单了