java数据结构中的链表，你知道多少？

愚公要移山 07-17 222

前言：

目前小伙伴们对“java合并两个排序的链表”可能比较注重，同学们都需要了解一些“java合并两个排序的链表”的相关内容。那么小编也在网上收集了一些对于“java合并两个排序的链表””的相关知识，希望我们能喜欢，姐妹们一起来了解一下吧！

为什么要讲链表呢？这是因为java中有很多集合类底层都是通过链表来实现的。而且面试的时候，链表的实现是经常考的一个知识点。所以这篇文章的重点在于，如何使用代码去实现这些数据结构。但是这篇文章我不打算直接上来就讲链表，而是先从线性表开始。按照惯例先给出这篇文章的大致脉络吧。

首先，是对数据结构中线性表，做一个回顾。还讲了其两大存储结构，顺序存储结构和链式存储结构。

接下来，重点讲各种链表的介绍，以及常用方法和特点

最后，对java中使用链表的集合类，进行一个介绍。

当然，还有一些常见的面试题。

OK，开始。

一、线性表

为了很好的描述这个概念，先从一个例子开始吧，比如幼儿园的小朋友放学之后，都是手拉手排着队走出校园，这些小朋友从外表来看就像是一条链子，而线性表就和这个链子一样，这些小朋友就像是线性表里面的数据元素，从外面看一个接一个。比较正式的定义那就是：线性表：0个或者多个数据元素的有限序列。

刚刚我提到的都是从表面来看都是一样的，说明在内部的实现方式是不一样的，下面就是线性表的两种存储结构：顺序存储结构和链式存储结构。

顺序存储结构：用一段地址连续的存储单元依次存储线性表的数据元素。链式存储结构：地址可以连续也可以不连续的存储单元存储数据元素

今天主要讲的就是基于链式存储结构的链表。你可以这样理解，比如说你要找一个人，名字叫张三，你首先跑到A，发现没有，A告诉你B可能知道，你跑到了B。B说C可能知道，你跑到了C，张三果然在C那里，如果没有就这样一直不停的去找。一张图看一下

但是这只是基础，对线性表的描述，不想花费太多时间在这。下面用一张图表述吧。

有了上面这张图，相信对分类等都有了了解和认识了。下面开始今天的主题链表。

下面在对这两种存储结构进行一个对比。

二、链表

1、单链表

对于链表，里面主要有几个重要的信息，对于每一个节点（比如上一节讲到的A,B,C三处）都有下一个节点的地址和当前节点的数据。下面代码实现一下：

首先是节点的定义：

public class Node<T> { private T data; //节点的数据 public Node next; //指向的下一个节点 public Node(T data, Node next) { this.data = data; this.next=next; }  public Node() { } public T getData() { return data; } private void setData(T data) { this.data = data; } }

接下来无非是对节点的增删改查罢了，先看基本的操作。

public class LinkList<T> { private Node head; //头结点 private Node tail; //尾结点 private int size; //链表长度 public LinkList() { head=null; tail=null; } //获取链表长度 public int getLength(){ return size; } //是否含有元素 public boolean isEmpty(){ return size==0; } //清空链表 public void clear(){ head=null; tail=null; size=0; } //通过索引获取节点 public Node getNodeByIndex(int index){ if(index<0||index>size-1){ throw new IndexOutOfBoundsException("索引越界"); } Node node=head; for(int i=0;i<size;i++,node=node.next){ if(i==index){ return node; } } return null; }}

下面就是正删改查了，但是有一个思路需要我们要牢记，这样在使用其他语言实现的时候，就能快速的掌握，这是我自己的方法。上面已经描述了通过索引查找元素，所以下面只考虑，插入删除操作就好了。

首先，我们要判断当前的空间是否满足增删该查的条件

接下来，判断增删改查的位置是否正确

最后，增删改查之后没有副作用产生。

第一个操作：插入（三种方式：头插入、尾插入、中间插入）

对于插入操作，使用一张图简单表述一下

 //头插入 public void addAtHead(T element){ head=new Node<T>(element, head); //如果是空链表就变让尾指针指向头指针 if(tail==null){ tail=head; } size++; }  //尾插入 public void addAtTail(T element){ //如果表为空 if(head==null){ head=new Node<T>(element, null); tail=head; }else{ Node node=new Node<T>(element, null); tail.next=node; tail=node; //尾节点后移 } size++; }  //在指定位置插入元素 public void insert(T element,int index){ if(index<0||index>size){ throw new IndexOutOfBoundsException("索引越界"); } if(index==0){ addAtHead(element); }else if(index>0&&index<size-1){ //中间插入 Node nexNode=null; Node insNode=new Node<T>(element, nexNode); nexNode=getNodeByIndex(index); Node preNode=getNodeByIndex(index-1); preNode.next=insNode; insNode.next=nexNode; size++; }else { addAtTail(element); } }

第二种操作：删除

对删除操作同样一张图

 public void delete(int index){ if(index<0||index>size-1){ throw new IndexOutOfBoundsException("索引越界"); } int flag=index-1; Node node=getNodeByIndex(index); if(flag < 0){ //flag<0说明删除的是第一个元素，将头结点指向下一个就行 head=head.next; node=null; }else{ //在这里才是真正的删除操作， Node preNode=getNodeByIndex(index-1); preNode.next=node.next; //如果删除的是最后一个元素，尾节点前移一位 if(index==size-1){ tail=preNode; } } size--; }  //删除最后一个元素 public void remove(){ delete(size-1); }

小结：上述是对单链表的增删改查操作，对于其他链表关键就在于对单链表的更改。当然这里只给出了链表的代码实现。对于顺序存储结构的顺序表实现。同样也是这个道理。你只需要定义一个节点进行增删改查就好了。

2、循环链表

如果你对单链表的操作能够掌握的话，剩下的这几种链表，我相信你也能很快掌握，只不过把node中的基本数据改一下，增删的时候多一两行代码。对于循环链表，你可以想象成y一个闭环的链表。也就是最后一个元素又指向了第一个元素。其特点是这里的讨论重点。

特点

（1）适合合并两个循环链表：有了尾指针直接合并，比如说下面有两个循环链表。

现在使用尾指针合并他们。

（2）从表中任何一个节点出发，都能访问链表的全部节点。这一点很好理解。

3、双向链表

从名字就可以看出，每一个节点既指向前驱又指向后继。

这个双向链表相对于单链表还是比较复杂的，毕竟每个节点多了一个前驱，因此对于插入和删除要格外小心。双向链表的优点在于对每个节点的相邻接点操作时候，效率会比较高。

三、java中的线性表表

最典型的就是Collection接口了。下面还包括了一些他的实现类，比如List接口，ArrayList类和LinkList类，其底层都是实现了线性表。详细的我已经整理了一部分到我的微信公众号了（java的架构师技术栈）。因为我最近才开始真正的写文章，所以里面的内容我在一点一点丰富填充。