Java数据结构之线性表

Java数据结构之线性表

线性表是其组成元素间具有线性关系的一种数据结构，对线性表的基本操作主要有，获取元素，设置元素值，遍历，插入，删除，查找，替换，排序等。而线性表可以采用顺序储存结构和链式储存结构，本节主要讲解顺序表、单链表以及双链表的各种基本操作。

1：线性表抽象的数据类型

线性表：是由n（n>=0）个数据相同的元素组成的有限序列。线性表的定义接口如下

public interface IList {

/**

* 是否为空

* @return

*/

boolean isEmpty();

/**

* 表的长度

* @return

*/

int length();

/**

* 根据索引获取长度

* @param i

* @return

*/

T get(int i);

/**

* 设置第i个元素值为x

* @param i

* @param x

*/

void set(int i,T x);

/**

* 在线性表最后插入x元素

* @param x

*/

void append(T x);

/**

* 异常第i个元素并返回值

* @param i

* @return

*/

T remove(int i);

/**

* 删除线性表中所有元素

*/

void removeAll();

/**

* 查询首次出现关键字为key的元素

* @param key

* @return

*/

T search(T key);

void insert(int i,T x);

/**

* 升序添加

* @param x

*/

void insert(T x);

/**

* 升序删除

* @param x

*/

void remove(T x);

}

2：线性表顺序表示和实现

线性表的顺序存储结构是一组连续的内存单元依次存放的线性表的数据元素，元素的物理地址和逻辑地址次序是相同的。我们叫做这种存储方式为顺序表。

由于数组只能进行赋值和取值，而且长度是不可变化的，所以给我们的操作带来很大的麻烦，但是用顺序表就可以进行删除，插入等操作。其实顺序表内部同样适用数组来表示的，只不过这个数据我们可以改变他的长度，这样说来我们就好办了，首先我们要为顺序表定义一个数组，同时在定义一个值来记录线性表的长度，所以第一步我们就有了如下

准备事件做好了以后，我们肯定会对顺序表进行初始化，刚刚开始数组的长度肯定是0。但是我们必须要为数组开辟一个内存空间，来存储要插入的元素，如下

其他的都比较简单，我主要说下插入和删除

插入一个元素的时候，如果插在第i个位置，那么意味着它后面所有的元素前部往后面移一位，但是我们必须把i个位置留出来给即将插入的元素。但是我们还必须考虑，如果这个数组满了的情况。如果满了，我们必须重新为顺序表开辟内存空间，然后把以前的元素进行迁移到新的表中，java实现如下

代码看出，我们把从第i个位置的元素全部往后移（包括第i个元素）然后在把第i个元素进行赋值

删除第i个元素，这个和上面的正好相反，如果删除第i个元素意味着在i之后的元素前部往前移一位。

3：顺序表操作效率分析

因为顺序表是具有索引的，所以get()和set()效率极高，时间复杂度都是O(n)。

从上面发现，在插入和删除的时候都是需要大量元素的移动，因为在各个位置插入元素的概率相同，所以平均插入一个元素要移动的元素是2/n。那么它的时间复杂度就是O(n)，如果要容器满了，那么就需要申请更大的容器来存储新加入的元素，那么效率会更加的低下。所以顺序表的静态性好，动态性就很差了，所以在选择的时候就要注意一下。

4：单链表的实现

线性表的链式存储结构是用若干地址分散的存储单元存储数据元素，逻辑上相邻的2个元素，物理地址不一定相同，这么说来就充分的利用了内存中的地址。但是我们必须用附加信息来连接2个不同的数据元素，所以这里就引进了2个概念，数据域(data)和地址域(next)，其中数据域存储的是这个元素的值，地址域存储下一个元素的地址。其中数据域和地址域联合起来我们称为节点（node）。如果只有后继节点没有前驱节点我们就称为单链表，那么现在我们来看看单链表的实现。

首先我们要定义一个节点Node

public class Node {

public T data;//数据域

public Node next;//地址域

public Node() {

this(null, null);

}

public Node(T data, Node next) {

this.data = data;

this.next = next;

}

}

现在我们想象一下，A(x)和B(y)2个节点，其中A的后继节点是B，那么我们怎么表示呢，如下

Node A=new Node(x,null);

Node B=new Node(y,null);

A.next=B。

也可以把A写成Node A=new Node(x,B);

ok现在我们正式开始实现一个带有头节点的单链表

我们可以把头指针想象成一个指针来便于我们的操作，我们先看如何实现单链表的长度

public int length() {

int i = 0;

Node p = this.head.next;

while (p != null) {

p = p.next;

i++;

}

return i;

}

因为这是一个链式的结构，我们无法得知长度，只能通过循环来知道链表中节点的个数，因为头指针的后继节点就是我们链表中第一个节点，所以我们就可以这样往下循环来得知。

获取第i个节点的值

同样我们无法直接获取节点，这个时候同样采用循环，如果循环第i个元素值等于我们i那么我们就获取这个节点，然后得到值

public T get(int i) {

if (i >= 0) {

Node p = this.head;

for (int j = 0; j <= i; j++) {

p = p.next;

}

if (p!=null){

return p.data;

}

}

return null;

}

在第i个位置插入一个节点

首先我们必须要找到要插入节点的前驱节点,然后前驱节点的后继节点指向这个新节点，新节点的后继节点指向原来前驱节点的后继节点。

从代码看出我们是根据头节点进行循环的。加入p.next!=null的目的是为了当循环到最后一个节点的时候就停止，不在继续了。

移除第i个节点

如果我们要删除第i个节点和上面差不多，同样我们要找到这个第i个节点的前驱节点，和上面代码差不多。

在链表后追加一个节点。

如果传统的话我们可以采取insert(this.length,x);但是这样一来计算长度的时候就需要遍历链表无疑速度减慢，只需要如下

insert(Integer.MAX_VALUE, x)即可，从插入代码可以看到当循环到最后一个节点就不会继续了，然后把新的节点加入最后即可。

5：排序单链表

排序首先我们需要我们的元素要继承comparable。

我们就说插入和删除。先说插入

如果插入一个元素，我们先获取要插入这个节点的前驱节点和后继节点。（x.compareTo(y)<0 表示小于y）

其中p.data.next.compareTo(x)<0如果跳出循环说明p节点值大于或等于x

如果删除一个元素，和上面的基本一样，但是要加上一个判断如下

其中通过上面判断我们知道p节点大于或等于x节点了，所以需要再次判断。

6：单链表操作效率分析

单链表在获取元素和设置元素的时候都需要进行遍历所以时间复杂度O(n)

如果在p节点插入或删除元素，只需要修改链的后继节点的地址即可所以时间复杂度O(1),但是如果插入类似insert(i,x)就需要进行遍历了，那么时间复杂度就是O(n).

对单链表进行插入和删除只需要改变少量节点的链，不需要移动元素，单链表的插入和删除都是动态申请和释放的，不需要预先分配存储空间，从而不会因为存储空间不足而进行扩容，提高了运行效率。

7：双链表的实现

双链表和单链表大多是相同的只不过多了前驱节点，现在我们先定义一下双链表

我们这里来演示循环双链表的实现。基本和单链表相同只不过如果为空链表那么它的后继节点就是头节点。ok我们先来看

求双链表的长度（基本和单链表一样后面一样的不在写了）因为是循环双链表最后一个节点的后继节点为

我们这里只说插入和删除（其他基本一样和单链表）

插入

同样我们需要找到要插入的节点

其中p.next!=this.head表示如果是最后一个节点则跳出循环。其中要插入的节点在p节点之后，然后我们就好理解了。

删除

和上面的差不多

8：循环双链表

根本和单链表一样。也是先找到节点的位置然后插入PEypTgKPEq或删除

总结：主要是回顾一下线性表，通过对线性表的了解，在以后我们看java容器源码的时候会带来极大的帮助

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。