数据结构——链表（Java）
顺序表
顺序存储的线性表，是由n个数据元素所构成的有限序列。
特点
- 不仅逻辑上相邻，物理地址上也相邻。（静态存储）
- 存储密度高，在物理地址上占有连续的存储址空间，需要预先分配好一块连续的地址存储空间。
- 便于随机存取。
- 不便于插入和删除，因为该操作会引起大量的数据移动，会引起平均约一般的数据移动。
图片参考自：https://blog.****.net/kevin_nan/article/details/85678495
线性表一般包括八种方法，如下：
public class SqList
void clean(); //链表置空
boolean isEmpty(); //判空
int length(); //判断长度
Object get(int i); //获取第i个元素
insert(int i,Object x); //向第i个位置插入元素
void remove(int i); //移除第i个位置的元素
int indexOf(Obect x); //查找第一个出现元素x的位置
void display(); //遍历输出
具体实现：
package LinkedDemo;
public class SqList {
private Object[] listElem; //顺序表
private int curLen; //顺序表有效长度
public SqList(int maxSize) {
curLen = 0;
listElem = new Object[maxSize];
}
public SqList(Object[] arr) {
curLen = arr.length;
listElem = arr;
}
//置空
public void clean() {
curLen = 0;
}
//判空
public boolean isEmpty() {
return curLen == 0;
}
//返回有效长度
public int length() {
return curLen;
}
//取第i个元素
public Object get(int i) throws Exception{
if(i<0 || i>curLen-1)
throw new Exception("第"+i+"个元素不存在");
return listElem[i];
}
//向第i个位置插入元素x
public void insert(int i,Object x) throws Exception {
if(curLen == listElem.length)
throw new Exception("顺序表已满");
for(int j=curLen-1;j>i;j--) {
listElem[j] = listElem[j-1];
}
listElem[i] = x;
curLen++;
}
//移除第i个元素
public void remove(int i) throws Exception {
if(i<0 || i>curLen-1)
throw new Exception("删除位置不合法");
for(int j = i;j<curLen-1;j++)
listElem[j] = listElem[j+1];
curLen--;
}
}
链表
链表是链式存储的线性表，是一种递归的数据结构，它或者为空（null），或者是指向一个结点（node）的引用，且该结点含有一个泛型的元素（数据域）和指向另一条链表的引用（指针域）。
特点
- 逻辑顺序相邻，物理地址存储任意。（动态存储）
- 便于插入和删除，时间复杂度都为O（1）。
- 只能顺序存取。
链表结构依赖于结点类，可以说是对各个结点的集合操作。因为结点是一个可能含有任意类型数据的抽象实体，我在这里使用了泛型来建立一个结点类。
package LinkedDemo;
public class Node<T> {
/**
* 用来存放结点的值
*/
public T data;
/**
* 用来存放后续的结点的引用
*/
public Node<T> next;
public Node() {
// 调用有两个参数的构造方法Node(T data,Node<T> next)
this(null,null);
}
public Node(T data) {
// 同理
this(data,null);
}
public Node(T data,Node<T> next) {
this.data = data;
this.next = next;
}
}
跟顺序表的操作相同，链式存储操作同样包含以下8钟方法。
public class DuLinkedList <T>
void clean(); //链表置空
boolean isEmpty(); //判空
int length(); //判断长度
T get(int i); //获取第i个元素
insert(int i,T x); //向第i个位置插入元素
void remove(int i); //移除第i个位置的元素
int indexOf(T x); //查找第一个出现元素x的位置
void display(); //遍历输出
分类
- 单链表：结点依次指向另一个结点
- 循环链表 ：首尾结点相连，尾结点指针域指向首结点
- 双向链表 ：一个数据域两个指针域，分别指向前驱和后继
- 双向循环链表：双向链表首尾相连
具体实现：
单链表
-
单链表的表示
不带头结点
带头结点（唯一标识） -
单链表的创建
类中使用head唯一标识一个单链表
public Node<T> head; // 头结点
插入操作：
// 向第i个位置插入一个数据为x的结点
public void insert(int i, T x) throws Exception {
Node<T> temp = head;
int j = -1;
while (temp != null && j < i - 1) {
temp = temp.next;
++j;
}
if (j > i - 1 || temp == null) {
throw new Exception("输入位置不合法");
}
Node<T> s = new Node<T>(x);
s.next = temp.next;
temp.next = s;
}
头插法创建：在head头结点之后插入，原先头结点之后的结点变为待插入结点之后
// 头插法插入结点 n为链表的长度
public void CreateListF(int n) throws Exception {
System.out.println("请输入链表数据");
Scanner sc = new Scanner(System.in);
for (int i = 0; i < n; i++) {
insert(0, (T) sc.next());
}
}
尾插法创建：在链表的尾结点之后插入结点
// 尾插法插入结点 n为链表的长度
public void CreateListR(int n) throws Exception {
System.out.println("请输入链表数据");
Scanner sc = new Scanner(System.in);
for (int i = 0; i < n; i++) {
insert(length(), (T)sc.next());
}
}
以上的头插法尾插法有一个困扰我挺久的问题，就是类型不统一的问题。因为用到了scanner类的控制台输入，就算指定了Integer或者其他类型，用了强制类型转化（T）sc.next() 也无法保证能够转化成功，类型仍会显示为String类型。如果是在main函数中再次调用insert方法传递类型会是正常 的。
-
单链表的删除操作
// 删除第i个节点
public void remove(int i) throws Exception {
Node<T> temp = head;
int j = -1;
while (temp.next != null && j < i - 1) {
temp = temp.next;
++j;
}
if (j > i - 1 || temp.next == null) {
throw new Exception("删除位置不合法!");
}
temp.next = temp.next.next;
}
- 单链表的其他操作
// 删除整个链表
public void clean() {
head.data = null;
head.next = null;
}
// 判断链表是否为空
public boolean isEmpty() {
return head.next == null;
}
// 判断链表长度
public int length() {
Node<T> p = head.next;
int length = 0;
while (p != null) {
p = p.next;
++length;
}
return length;
}
// 获取第i个结点的值
public T get(int i) throws Exception {
Node<T> temp = head.next;
int j = 0;
while (temp != null && j < i) {
temp = temp.next;
++j;
}
if (j > i || temp == null) {
throw new Exception("第" + i + "个元素不存在! ");
}
return temp.data;
}
// 删除值为x的结点
public void removeValue(T x) {
Node<T> temp = head;
while (temp.next != null) {
if (temp.next.data.equals(x.toString())) {
System.out.println("删除的结点值为："+temp.next.data);
temp.next = temp.next.next;
break;
}
temp = temp.next;
}
}
// 返回值为参数x的位置
public int indexOf(T x) {
Node<T> temp = head.next;
int j = 0;
while (temp != null && !(temp.data).equals(x.toString())) {
temp = temp.next;
++j;
}
if (temp != null) {
return j;
} else {
System.out.println("该值不存在!");
return -1;
}
}
// 输出整个链表
public void display() {
Node<T> node = head.next;
while (node != null) {
System.out.print(node.data + " ");
node = node.next;
}
System.out.println();
}
循环链表
在单链表的基础上将尾结点指向首结点，同样分为带头结点和不带头结点的循环链表。
// 带头结点链表循环 n为链表的长度(可用length())
public void cycle_connect(int n) {
Node<T> temp = head;
if (n<=length()&& n>=0) {
for (int i = 0; i < n; i++) {
temp = temp.next;
}
temp.next = head;
}
else
System.out.println("输入有误！");
}
// 不带头结点的链表循环
public void cycle_connect1(int n) {
Node<T> temp = head;
if (n<=length()) {
for (int i = 0; i < n; i++) {
temp = temp.next;
}
temp.next = head.next;
}
else
System.out.println("输入有误！");
}
双向链表
双向链表结点类如下：
public class DuLNode <T>{
/**
* 用来存放结点的值
*/
public T data;
/**
* 用来存放前面结点以及后续的引用
*/
public DuLNode<T> prior;
public DuLNode<T> next;
public DuLNode(){
this(null);
}
public DuLNode(T data) {
this.data = data;
this.prior = null;
this.next = null;
}
}
由于其他操作和单链表的操作类似，以下只给出插入和删除的操作，如下：
双向链表插入
// (带头结点)向第i个位置插入一个数据为x的结点
public void insert(int i, T x) throws Exception {
DuLNode<T> p = head.next;
int j = 0;
while (!p.equals(head) && j < i) {
p = p.next;
++j;
}
if (j != i && !p.equals(head)) {
throw new Exception("输入位置不合法!");
}
DuLNode<T> s = new DuLNode<T>(x);
p.prior.next = s;
s.prior = p.prior;
s.next = p;
p.prior = s;
}
双向链表删除
// 删除第i个节点
public void remove(int i) throws Exception {
DuLNode<T> p = head.next;
int j = 0;
while (!p.equals(head) && j < i) {
p = p.next;
++j;
}
if (j != i)
throw new Exception("删除位置不合法!");
p.prior.next = p.next;
p.next.prior = p.prior;
}
双向循环链表
在双向链表的基础上将首结点的前驱指向尾结点，尾结点的后继指向首结点。
总结
链表作为一个特别基础的数据结构，是在集合类的抽象数据类型实现中表述数据的合适选择，并且其应用十分广泛，应当是我们掌握并不断使用的。