对于有尾结点的链表，我这样想可不可以?
来源：4-7 带有尾指针的链表：使用链表实现队列
alexMerce
2018-07-01
在4-7章节中，为了实现队列，向链表中添加了Tail 尾结点。然而我认为还有可优化的余地。在链表中，可以用Node cur = head.next ; (循环 cur = cur.next ) 从头遍历到尾，但是并不能从尾遍历到头。如视频所言，这样链表是不对称的，那可不可以让链表对称？
链表只能从头往尾遍历， 那我可以在Node内部类中再添加一个属性Node prev,这样Node内部类中就有了三个属性:E data保存数据，Node next 指向下一个结点， Node prev指向上一个结点。
类似地，也可以来一个虚拟尾节点dummTail，在链表类的构造方法中，分别令dummyHead指向虚拟头结点，dummyTail指向虚拟尾结点，然后令dummyHead.next = dummyTail, dummyTail.prev = dummyHead , 而dummyHead. prev = null, dummyTail.next = null 。 这样就构造好了初始的链表
然后向链表中增添或者删除一个结点，先判断这个索引是离头结点还是离尾节点更近，如果index < size/2,说明离头近，从头遍历， 如果index > size/2 说明离尾近，从尾遍历。 遍历的方法都是类似的，都是设置一个临时指针temp,如果离头近，那么我就 Node temp = dummyhead ,(循环 temp =temp.next ) ； 如果离尾近，我就Node temp = dummyTail,(循环 temp = temp.prev) .
这样的话，添加头，添加尾 和 删除头，删除尾的时间复杂度都是1 . 这样的话，链表就对称了，意思是从头到尾进行操作，和从尾到头进行操作，并没有复杂度不同的问题。
不知道我这样想有没有合理性？
1回答
-
赞思考：）
首先，对于每一个节点，除了包含next，还包含prev，本身是一种很标准的链表实现方式，称为双链表（或者双向链表，Double Linked List）。在第五章最后，我会对更多链表形式进行简单的提及。强烈建议同学们在学习完单链表以后，自己编写一个双链表的类：）
你后面的分析完全合理：）
对于双链表，无论是头尾的添加还是头尾的删除，时间复杂度都是O(1)级别的；
同时对某个索引的添加和删除，可以使用你说的方法进行优化，不过时间复杂度依然是O(n)级别的：）
如果我们想删除指定元素（而非删除指定索引的元素），或者在添加元素的时候保持链表有序（而非在指定索引添加元素），依然要遍历整个链表，时间复杂度是O(n)的。
在大多数场景，我们使用单链表是足够的，比如使用基于链表的栈或者队列；
双链表最适合应用于在头尾都需要进行插入和删除的场景。有一种抽象的数据结构，叫做“双端队列”，通常叫deque，就是指在队列的两端均可以进行插入和删除元素的数据结构。deque的底层实现如果使用链式结构，就需要使用双端链表。当然，deque也可以使用动态数组来实现。有兴趣可以自己编写尝试一下，是一个很好的练习：）
加油！
022018-07-03
相似问题