【数据结构】：用Java实现链表

概念

顺序表是物理上连续，逻辑上也是连续的
链表是一种物理存储结构上非连续存储结构，数据元素的逻辑顺序是通过链表中的引用链接次序实现的 。

链表是由一个一个的节点组织起来的，整体的组织就叫链表

注意：

1. 从上图可看出，链式结构在逻辑上是连续的，但在物理上不一定连续
2. 现实中的节点一般都是从堆上申请出来的
3. 从堆上申请的空间，是按照一定的策略来分配的，两次申请的空间可能连续，也可能不连续

分类

链表

1. 单向/双向
2. 带头/不带头: 带头就是带一个头节点，头结点的数据域可以不存储任何信息，也可以用来存储一些附加信息，如链表的长度等。
3. 循环/不循环： 循环就是将最后一个节点里面地址改为第一个节点的地址

链表结构

1. 单向带头循环
2. 单向带头非循环
3. 单向不带头循环
4. 单向不带头非循环（重点）
5. 双向带头循环
6. 双向带头非循环
7. 双向不带头循环
8. 双向不带头非循环（重点）

链表的实现

链表的构造

节点的构造和连接

• 当一个事物的内部，还有一个部分需要一个完整的结构进行描述，而这个内部的完整的结构又只为外部食物提供服务，那么这个内部类的完整结构最好使用 内部类
• 因为链表是由若干节点组成，而节点又是一个完整的结构，所以将节点定义为内部类。其最少有两个域，一个是数值域，一个是 next域，且 next 的类型为节点类型
• 最后对节点进行构造，只需要实例化这个内部类的对象即可，实例化出来的对象便是节点

class listnode {  
    public int val;  
    public listnode next;  
  
    public listnode(int val) {  
        this.val = val;  
    }
}

public listnode head;  
  
public void createlist() {  
    listnode node1 = new listnode(12);  
    listnode node2 = new listnode(23);  
    listnode node3 = new listnode(34);  
    listnode node4 = new listnode(45);  
    listnode node5 = new listnode(56);    
}

• 通过访问 node1 存储地址的变量 next，将其的值赋为下一个节点的地址
• 以此类推
• 最后让头节点指向第一个节点 node1

node1.next = node2;  
node2.next = node3;  
node3.next = node4;  
node4.next = node5;  
	  
this.head = node1;

链表的功能

void display()——遍历链表

• 当 head == null 的时候，链表就遍历完了。若写成 head.next == null，则不会打印出最后一个节点的数据
• 要从第一个节点走到第二个节点，只需要 head == head. next 即可。
• 但若想完成多次打印，head 的位置就不能变，需要一直在首位，所以我们就定义一个 cur 节点，来做 head 的 遍历工作，head 只负责 站在最前面定位 即可

//遍历链表
public void display() {  
    listnode cur = head;  
    while (cur != null) {  
        system.out.print(cur.val + " ");  
        cur = cur.next;  
    }    system.out.println();  
}

int size()——求链表长度

1. 定义一个 count 变量，用来记录 cur 向后走的次数
2. 每向后走一步，count++

//计算链表长度  
public int size() {  
    int count = 0;  
    listnode cur = head;  
    while (cur != null) {  
        count++;  
        cur = cur.next;  
    }    return count;  
}

void addfirst(int val)——头插法

1. 将此时头结点的地址传给 node 的 next 变量
2. 将头节点前移到 node 的地方

//头插  
public void addfirst(int val) {  
    listnode node = new listnode(val);  
    node.next = head;  
    head = node;  
}

void addlast(int val)——尾插法

1. 为了避免产生空指针异常报错，我们先对 head == null 的情况进行讨论
   • 若头节点为空，则 head = node;
   • 记得加上 return，否则程序会继续执行下去
2. 若链表不为空，找到链表的尾巴
   • 当 cur. next == null 时，cur 指向的就是尾巴
3. 最后让 head.next == node; 即可

//尾插  
public void addlast(int val) {  
    listnode node = new listnode(val);  
    if (head == null) {  
        head = node;  
        return;  
    }    listnode cur = head;  
    while (cur.next != null) {  
        cur = cur.next;  
    }    cur.next = node;  
}

void addindex(int index, int val)——在任意位置插入

1. 判断 index 的合法性
   1. 定义一个 checkindex(int index) 方法用来检查 index 的合法性
   2. 若不合法，则抛出一个自定义异常：indexnotleagalexception
2. index == 0 || index == size();
   1. 前者相当于是头插，直接调用 addfirst()
   2. 后者相当于是尾插，直接调用 addlast()
3. 找到 index 的前一个位置
   1. 创建一个 findindexsubone(int index) 方法
   2. 创建一个节点 cur 来接收调用方法的返回值
   3. 最后 cur 就是 index 位置的前一个节点了
4. 进行连接
   1. 实例化一个所带数据为 val 的节点 node
   2. node.next = cur.next;
   3. cur.next = node;

//在任意位置插入  
public void addindex(int index, int val) {  
    //1. 判断index的合法性  
    try {  
        checkindex(index);  
    } catch (indexnotlegalexception e) {  
        e.printstacktrace();  
    }  
    
    //2. index == 0 || index == size()  
    if(index == 0){  
        addfirst(val);  
        return;  
    }    else if(index == this.size()){  
        addlast(val);  
        return;  
    }  
    
    //3. 找到 index 的前一个位置  
    listnode cur = findindexsubone(index);  
  
    //4. 进行连接  
    listnode node = new listnode(val);  
    node.next = cur.next;  
    cur.next = node;  
}  

//用来检查输入的 index 是否合法的方法
public void checkindex(int index) {  
    if(index < 0 || index > size()){  
    	//若不合法则抛出一个异常
        throw new indexnotlegalexception("index位置不合法");  
    }
}  

//用来找到 index 前一位对应的节点的函数
private listnode findindexsubone(int index) {  
    listnode cur = head;  
    for (int i = 0; i < index - 1; i++) {  
        cur = cur.next;  
    }    return cur;  
}

boolean contains(int val)——链表中是否包含某个元素

1. 遍历链表
2. 若能在链表元素中找到 val 值，则返回 true
3. 否则返回 false

//判断链表中是否包含某个元素  
public boolean contains(int val) {  
    listnode cur = head;  
    while(cur != null){  
        if(cur.val == val){  
            return true;  
        }    
    }    
    return false;  
}

void remove(int key)——删除第一次出现的关键字的节点

1. 首先判断是否为空链表
2. 遍历链表
   • 循环条件为：cur.next != null
3. 找到 val 值的前一个节点 cur
   • 当 cur.next.val == val 时，找到目标
4. 进行删除
   • 找到之后，将其创建为 del 节点
   • cur.next = del.next 或者 cur.next = cur.next.next
   • 看表达式可知，删除的判断是从第二个元素开始的，无法对第一个元素进行判断，所以需要针对第一个元素再加上一个删除判断：head.val == val

//删除第一次出现的关键字的节点  
public void remove(int val) {  
    //链表为空  
    if(head == null){  
        return;  
    }    //当第一个元素就为 val    
    if(head.val == val){  
        head = head.next;  
        return;  
    }  
    
    listnode cur = head;  
    while(cur.next != null){  
        if(cur.next.val == val){  
            listnode del = cur.next;  
            cur.next = del.next;  
        }        
        cur = cur.next;  
    }
}

void removeall(int val)——删除所有出现的关键字的节点

在原有的链表上进行修改
只遍历一遍链表

• 定义两个引用变量
  • cur 代表当前需要删除的节点
  • prev 代表当前需要删除节点的前驱

1. 若 cur.val == val
   1. prev.next = cur.next
   2. cur = cur.next
2. 否则：
   1. prev = cur
   2. cur = cur.next
3. 处理头节点

//删除所有出现的关键字节点  
public void removeall(int val) {  
    //1. 判空  
    if (head == null) {  
        return;  
    }  
    
    //2. 定义 prev 和 cur    
    listnode prev = head;  
    listnode cur = head.next;  
  
    //3. 开始判断并删除  
    while (cur != null) {  
        if (cur.val == val) {  
            prev.next = cur.next;  
        } else {  
            prev = cur;  
        }        
        cur = cur.next;  
    }    
    //4. 处理头结点  
    if (head.val == val) {  
        head = head.next;  
    }
}

void clear()——清空

回收对象，防止内存浪费

//清空链表  
public void clear() {  
    head = null;  
}