数据结构与算法Java版——双向链表

淩亂°似流年 2022-06-13 02:15 154阅读 0赞

> 　　今天分享的是双向链表的实现，双向链表其实很容易实现，只需要在节点Node类加一个前置节点的属性，再让其指向上一个节点就可以完成，还要注意的点就是双线链表的查询操作可以从head节点或tail节点开始，即双向查询。其他步骤和单链表就相似了。
> 
> 　　这个学期学习的数据结构这本书，所以我打算用Java实现其中表，队，栈，树。如果你有兴趣可以持续关注我后续操作。我的CSDN地址为

public Node getNodeByIndex(int index){
            if(index<0||index>size-1){
                throw new IndexOutOfBoundsException("索引越界");
            }
            //如果索引在前半段，则从head开始向后搜索，否则从tail开始向前搜索
            if(index<=size/2){
                Node node=head;
                for(int i=0;i<=size/2;i++,node=node.next)
                {
                    if(i==index)
                    {
                        return node;
                    }
                }
            }else{
                Node node=tail;
                for(int i=size-1;i>size/2;i++,node=node.pre)
                {
                    if(i==index)
                    {
                        return node;
                    }
                }
            }
    
        }

基本上单链表与双向链表区别就在这一部分，**剩下的只需要注意插入删除节点时，需要记得是双向的，新插入的节点pre和next都需要分别指向前后节点，删除也要两边都要断开**就像下图所示：

![这里写图片描述][83436648.jpg]

剩下的操作就和单链表一样了，如果有何不明白可以参考我上一篇文章:[数据结构与算法Java版——单链表的实现][Java]，到此所有表的实现就基本完成了。

我们学习Java其实经常用到表，List就是我们常用的表，ArrayList就是顺序表的实现，LinkList是双向链表，两者各不同，所以用表的时候一定要考虑常用操作是什么，再来选择用什么表，最后附上两者优点与缺点表：

<table> 
 <tbody> 
  <tr> 
   <td></td> 
   <td>顺序表</td> 
   <td> 链表 </td> 
  </tr> 
  <tr> 
   <td> 优点 </td> 
   <td>顺序表中逻辑顺序与物理存储顺序一致，所以查找和读取时行性能强大</td> 
   <td>链表采用链式结构保存元素，所以插入删除时性能好；存储空间是动态分布的，因此空间不会像数组一样浪费。</td> 
  </tr> 
  <tr> 
   <td>缺点</td> 
   <td>每个顺序表底层都是一个数组实现的，所以存在着部分内存浪费；执行插入和删除时性能不好，可能需要移动大量的元素。</td> 
   <td> 链表需要空间保存指针，所以会要牺牲一些空间。 </td> 
  </tr> 
 </tbody> 
</table>

[83436648.jpg]: http://or0um8wrx.bkt.clouddn.com/17-6-21/83436648.jpg
[Java]: http://xichangblog.com/2017/06/21/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84Java%E7%89%88%E2%80%94%E2%80%94%E5%8D%95%E9%93%BE%E8%A1%A8%E7%9A%84%E5%AE%9E%E7%8E%B0/