java常见线性结构图文实例源码介绍。常用的线性结构有：线性表，栈，队列，数组。线性表中包括顺序表、链表等，其中，栈和队列是特殊的线性表，只是属于逻辑上的概念，实际中不存在，仅仅是一种思想，一种理念；线性表则是在内存中数据的一种组织、存储的方式。

注意,哈希表是一种散列表:

若结构中存在关键字和K相等的记录，则必定存储在f(K）的位置上。由此，不需比较便可直接取得所查记录。这个对应关系f称为散列函数(Hash function），按这个思想建立的表为散列表。

线性结构是一个数据元素的有序集合。它有四个基本特征：

  1．集合中必存在唯一的一个”第一个元素”；

  2．集合中必存在唯一的一个”最后的元素”；

  3．除最后元素之外，其它数据元素均有唯一的”后继”；

  4．除第一元素之外，其它数据元素均有唯一的”前扑”。

  数据结构中线性结构指的是数据元素之间存在着“一对一”的线性关系的数据结构。

 

顺序表

顺序表将元素一个接一个的存入一组连续的存储单元中，在内存物理上是连续的。如下图：

 顺序表存储密度较大，节省空间；但需要事先确定容量，在时间性能方面，读运算较快，时间复杂度为O(1)；查找运算为O(n/2)，和链表同样；插入运算和删除运算如果要操作中间一个元素，比如3，那么就需要把3后面的元素全部进行移动，因此时间复杂度相对链表要大一些，插入时间复杂度最好为O(0)或最坏为O(n)；删除时间复杂度为O([n-1]/2)；

链表

链表拥有很多结点，每个结点前半部分是数据域，后半部分是指针域，指针域指针指向下一个结点；链表可分为单链表、循环链表和双链表。

单链表：

 从上图可以看出，单链表的上一个结点指针指向下一个结点，最后一个结点的指针域为null。

结点的删除：

 

删除一个结点，如删除上图中q结点，只需将p结点中的指针域指向a3，然后将a2释放掉（free）即可。

 

结点的插入：

 插入一个结点，如插入上图中s结点，首先将s的指针域指向a2（也就是把s的next赋值为p的next），然后将p结点的指针域指向x即可（p的next指向x）。

循环链表

 循环链表与单链表唯一不同之处是，循环链表的最后一个结点指针不为空，而是指向头结点。结点的插入和删除和单链表非常相似，就不再示范了。

双链表

 双链表拥有一前一后两个指针域，从两个不同的方向把链表连接起来，如此一来，从两个不同的方向形成了两条链，因此成为双链表。因此，双链表的灵活度要大于单链表。

结点的删除：

 

双链表的操作比单链表要稍显复杂（按照单链表思路来做其实也不难），如上图，要删除p节点，首先需要将a1的后驱指向a3，然后将a3的前驱指向a1，最后将p节点释放掉即可。

 

结点的插入：

 

如上图，插入q结点，首先要按照方向，将步骤拆分，首先将q节点的前驱指向p结点后驱，紧接着将x后驱指向a2；然后按照顺序完成图中所示的3、4步即可。

从空间性能来看，链表的存储密度要差一些，但在容量分配上更灵活一些。从时间性能来看，查找运算与顺序存储相同，插入运算和删除运算的时间复杂度为O(1)，要更优于顺序存储，但读运算则弱一些，为O([n+1]/2)，最好为1，最坏为n。

栈

 

上面提到栈属于一个逻辑概念，栈的实现可以用顺序也可以用链式。它遵循先进后出原则，如下图：

 

 

import java.util.Stack;  

 

public class TestStack {  

 

    public static void main(String[] args) {  

          

        Stack<String> stack = new Stack<String>();  

        stack.push(“NO1″);  

        stack.push(“NO2″);  

        stack.push(“NO3″);  

          

        System.out.println(“初始数量：” + stack.size());  

 

        while(!stack.isEmpty()){  

            System.out.println(stack.pop());  

        }     

          

        System.out.println(“取完后的数量：” + stack.size());  

    } 

} 

队列

 

队列遵循先进先出的原则，如下图：

 package Stream;

 

import java.util.Queue;

import java.util.LinkedList;

 

public class a {

public static void main(String[] args) {

Queue<String> queue = new LinkedList<String>();

queue.offer(“NO1″);

queue.offer(“NO2″);

queue.offer(“NO3″);

System.out.println(“初始数量” + queue.size());

String str;

while ((str = queue.poll()) != null) {

System.out.println(str);

}

System.out.println(“取出后数量” + queue.size());

}

}