[数据结构]单向链表 - pod4g/tool GitHub Wiki

/**
 * 单向链表
 * 由于在javascript中没有指针，所以可以用引用来模拟指针
 */
 class Node {
     constructor (data, next) {
         this.data = data
         this.next = next
     }
 }
 /**
  * 单向链表的整表创建
  * @param {nunber} n 创建长度为n的链表
  * @returns 
  * 头插入法
  */
 function createSingleLinkedListByHeadInsert (n) {
    let i
    // 生成头节点
    let head = new Node()
    for (i = 0; i < n; i++) {
        let node = new Node(i)
        node.next = head.next
        head.next = node
    }
    return head
 }

 /**
  * 单向链表的整表创建
  * @param {nunber} n 创建长度为n的链表
  * @returns 
  * 尾插入法
  */
 function createSingleLinkedListByTailInsert (n) {
    let i
    // 生成头节点
    let head = new Node()
    // 尾节点
    let tail = head
    for (i = 0; i < n; i++) {
        // 生成一个新节点
        let node = new Node(i)
        // 尾节点的next指向这个新节点
        tail.next = node
        // 更新当前的尾节点为这个新节点
        tail = node
    }
    return head
 }
 let linkedList = createSingleLinkedListByHeadInsert(10)
 let linkedList2 = createSingleLinkedListByTailInsert(10)
//  console.log(JSON.stringify(linkedList))
//  console.log(JSON.stringify(linkedList2))
 
 /**
  * @param {object} linkedList 
  * @param {number} 单向链表的第i个元素
  * 找到单向链表的第i个元素，并把其值返回
  */
 function getElem (linkedList, i) {
    let j = 1
    let p = linkedList.next
    while (p && j < i) {
       p = p.next
       ++j
    }
    if (!p || j > i) {
        return null
    }
    return p.data
 }
 

 let val = getElem(linkedList, 9)
//  console.log(val)
 
 /**
  * @param {object} linkedList 
  * @param {number} i 
  * @param {any} val 
  * @returns 在单向链表第i个元素之前，插入一个新节点，数据为val
  */
 function linkedListInsert (linkedList, i, val) {
    let j = 1
    let p = linkedList.next
    // 找到第i-1个元素，此元素即为第i个元素之前的元素
    while (p && j < i - 1) {
        p = p.next
        ++j
    }
    if (!p || j > i - 1) {
        return linkedList
    }
    // 新建一个节点，值为val
    let node = new Node(val)
    node.next = p.next.next
    p.next = node
    return linkedList
 }

 console.log(JSON.stringify(linkedListInsert(linkedList2, 5, 999)))
 
 /**
  * @param {object} linkedList 
  * @param {number} i 
  * @returns 返回被删除的值
  */
 function linkedListDelete (linkedList, i) {
     let j = 1
     let p = linkedList.next
     while (p && j < i - 1) {
         p = p.next
         ++j
     }
     if (!p && j > i - 1) return null
     let q = p.next
     let val = q.data
     p.next = q.next
     q = null
     return val
 }
 /**
  * @param {object} linkedList 
  * 删除指定的单链表
  */
 function linkedListClear (linkedList) {
    let p, q
    p = linkedList.next
    while (p) {
        q = p.next
        p = null
        p = q
    }
    p = null
 }
 
 console.log(JSON.stringify(linkedListClear(linkedList2)))
 linkedListClear(linkedList2)