数据结构与算法-循环链表与双向链表【四】-蒲公英云

数据结构与算法-循环链表与双向链表【四】

悠悠 2023-06-24 08:13 35阅读 0赞

我们下面讨论的前提是：

1，链表有一个辅助头节点，这个辅助头结点的next才是真正的数据节点。

2，单链表的定义：

// Definition for singly-linked list.
  function ListNode(val) { 
      this.val = val;
      this.next = null;
  }

循环链表

单链表只有一个头结点和一个尾节点。

循环链表：作为特殊的单链表的一种，尾节点的指针域，指向头结点，是一个闭环。【尾部指向头部】

循环链表遍历

单链表遍历完成的条件是 node == null

单循环连标遍历完成的条件是 node == head，head为头指针。

// 单链表遍历
    function iteratorList(node) { 
        while(node != null) { 
            console.log(node.val)
            node = node.next
        }
    }
    // 循环链表遍历
    function iteratorList(node) { 
        let head = node
        while(node.next != head) { 
            console.log(node.val)
            node = node.next
        }
    }

头指针和尾指针来表示单循环链表

也就是说，给予我们的指针是指向头节点和尾节点。

头指针表示的单循环链表，寻找第一个数据节点:R.next 时间复杂度为O(1)，寻找最后一个数据节点，时间复杂度为O(n)。

尾指针表示的单循环链表，寻找第一个数据节点:R.next.next，寻找最后一个数据节点，为R本身。时间复杂度都是O(1).

合并两个单循环链表

给我们的节点是尾指针节点。NodeA NodeB都是指向两个单循环链表的尾节点。

function mergeTwoLoopSingleList(Na, Nb) { 
        let p = Na.next // 保存头节点
        Na.next = Nb.next.next
        Nb.next = p
        return p
    }

双向链表

双向链表除了有一个数据域，有两个指针域，一个存前一个节点的地址，一个存后一个节点的地址。

因为节点本身存储了前驱和后继节点的地址，所以删除某个位置的元素以及在某个位置插入元素我们不一定非要找到前一个节点进行操作。

链表和顺序表的比较

链表是动态可变的
顺序表需要预先分配空间，会存在数据溢出或者空间闲置，存储空间不灵活。

链表插入和删除元素只需要移动指针即可。在确定位置的情况，时间复杂度为O(1)
顺序表插入删除元素会移动的元素,时间复杂度为O(n)

链表存取元素最坏的情况需要遍历整个链表，时间复杂度为O(n)
顺序表查找元素由于存储地址连续知道头元素，就能知道特定位置的元素的地址，时间复杂度为O(1)

顺序表是存取快，适合预先知道数据，不经常改变，但是经常存取的数据集合。
链表是插入删除快，适合经常动态变化的数据集合，

有序线性表的合并

顺序表的实现

用顺序表的实现，就可以理解为用数组来，也就是两个有序数组的合并，合并之后也需要是一个有序的。

看这里—> https://blog.csdn.net/a5534789/article/details/102669074

链表的实现

原理是类似的，但是比较好的方法是直接将某一个链表的head头指针作为新排序表的头节点，这样空间复杂度为O(1)

function mergeTwoOrderList(l1, l2) { 
        let n1 = l1.next, n2 = l2.next
        let newL = l1
        while(n1 && n2) { 
            if (n1.val <= n2.val) { 
                newL.next = n1
                n1 = n1.next
            } else { 
                newL.next = n2
                n2 = n2.next
            }
            newL = newL.next
        }
        // while(n1) { newL.next = n1 } 错误
        // 优化
        // if (n1) newL.next = n1
        // if (n2) newL.next = n1
        newL.next = n1 || n2
        return newL
    }