链表简介
前言
链表为数据结构中第二种基本结构，一般链表就是指在物理结构上非连续，非有序的数据结构，链表又分为单向链表和双向链表，单向链表一般可以如下定义
class Node{
// 链表节点存放数字
int data;
// 节点的后指针
Node next;
}
结构图如下
因为单向链表搜索顺序只能由左到右，显然对检索效率有一定影响，这时候就要推出双向链表，顾名思义就是在单项链表的基础上新增一个prev前指针既可以向前搜索也可以向后搜索，定义如下
class Node1{
// 链表节点存放数字
int data;
// 节点的后指针
Node next;
// 节点的前指针
Node prev;
}
结构图如下
链表的基本操作
为实现方便下面代码采用单项链表
链表插入操作
链表插入和数组插入同样需要考虑如下的问题
队头插入
将一个新的Node节点从链表的头部插入，注意这里不用像数组一样还需要移动其它元素，这个过程分为两步
- 将新的Node节点的next指针指向原Head头节点。
- 链表 Head头节点指向新Node节点。
队尾插入
队尾插入和队头插入类似，同样分为两步
- 将新的Node节点next指针置为 null 。
- 将原队尾节点的next指针指向新的Node节点
中间插入
中间插入和其余两种完全不同，这个过程分为三个步骤
- 获取插入位置的 前一个 元素，因为链表是单向的，直接获取插入位置元素后将无法获取插入位置前的元素。
- 将新Node节点的next指针指向需要插入的位置。
- 将插入位置的前一个元素的next指针指向新的Node节点，形成链表。
按照这个思路整理代码如下
public class LinkedDemo {
/**
* 定义单向链表节点
*/ private static class Node{
// 链表节点存放数字
int data;
// 链表的下一个节点
Node next;
public Node(int data){
this.data = data;
this.next = null;
}
@Override
public String toString() {
return "Node{" +
"data=" + data +
", next=" + next +
'}';
}
}
// 头指针
private Node head;
// 尾指针（为了尾部插入方便）
private Node last;
// 链表长度
private int size;
/**
* 链表插入
* @param index
* @param date
*/ public void insert(int index,int date){
if (index < 0 || index > size){
throw new Runtime Exception ("下标值有误");
}
Node insertData = new Node(date);
if (size == 0){
// 空链表
head = insertData;
last = insertData;
} else if (index == 0){
// 队头插入
insertData.next = head;
head = insertData;
}else if(index == size){
// 队尾插入
last.next = insertData;
last = insertData;
}else {
// 链表中间插入
// 先要去获取index下标的前一个Node节点（注意不是index下标的节点）
Node indexNode = getIndexNode(index-1);
insertData.next = indexNode.next;
indexNode.next = insertData;
}
size++;
}
public void show(){
Node temp = head;
do {
System.out.println(temp.toString());
temp = temp.next;
}while (temp!=null);
}
/**
* 获取执行下标的Node节点
* @param index 下标应该位于[0,size)之间
* @return
*/ public Node getIndexNode(int index){
Node temp = head;
for (int i = 0; i < index ; i++) {
temp = temp.next;
}
return temp;
}
public static void main(String[] args) {
LinkedDemo linkedDemo = new LinkedDemo();
linkedDemo.insert(0,12);
linkedDemo.insert(1,33);
linkedDemo.insert(2,45);
linkedDemo.insert(3,3);
linkedDemo.insert(0,999);
linkedDemo.show();
}
}
链表删除操作
理解了链表的插入操作，链表的删除操作也是类似了，同样分为三种方式
队头删除
队头节点就是head，那么删除步骤分为
- 获取队头节点的下一个节点newHead。
- 将原对头节点的next指针置为NULL，对于 JAVA 语言对象回收由GC处理，所以只需要让Node对象无引用即可。
- 将head头节点指向原头节点的下一个节点newHead。
队尾删除
队尾删除的关键就是获取队尾的前一个节点，将队尾的前一个节点的next指针置为NULL即可。
中间删除
中间删除较为复杂分为如下几步
- 获取删除元素的前一个节点和后一个节点。
- 将删除元素的next指向指向NULL。
- 将删除元素的前一个节点指向删除元素的后一个节点。
综上删除代码如下
/**
* 删除元素
*/ public void delete(int index){
if (index < 0 || index >= size){
throw new RuntimeException("下标值有误");
}
if (index == 0){
// 队头删除
Node next = head.next;
head.next = null;
head = next;
}else if (index == size){
// 队尾删除
// 获取队尾的前一个节点
Node node = getIndexNode(index - 1);
last = node;
}else {
// 获取index节点的前一个节点
Node beforeNode = getIndexNode(index - 1);
// 获取index节点的后一个节点
Node afterNode = beforeNode.next.next;
// index下标的节点
Node node = beforeNode.next;
node.next = null;
beforeNode.next = afterNode;
}
size--;
}
至于查询和修改操作不涉及到指针变化，但由于链表的存储特点，所以查询和修改都需要遍历链表才能完成，所以查询和修改的时间复杂度为O(n)，而插入和删除的时间复杂度为O(1)，这正好和数组的特征相反。
综上数组的优点是快速定位所以读多写少的场景会很适合，而链表的优势在于插入和删除更加灵活。
