链表
链表
强烈推介IDEA2020.2破解激活，IntelliJ IDEA 注册码，2020.2 IDEA 激活码
单链表是一种链式存取的数据结构，用一组地址任意的存储单元存放线性表中的数据元素。链表中的数据是以结点来表示的，每个结点的构成：元素(数据元素的映象) + 指针(指示后继元素存储位置)，元素就是存储数据的存储单元，指针就是连接每个结点的地址数据。链表是有序的列表，但是它在内存中是存储如下：
一、单链表介绍
【1】一种最简单的结点结构如图所示，它是构成单链表的基本结点结构。在结点中数据域用来存储数据元素，指针域用于指向下一个具有相同结构的结点。因为只有一个指针结点，称为单链表：
【3】在单链表结构中还需要注意的一点是，由于每个结点的数据域都是一个 Object 类的对象，因此，每个数据元素并非真正如图中那样，而是在结点中的数据域通过一个 Object类的对象引用来指向数据元素的。与数组类似，单链表中的结点也具有一个线性次序，即如果结点 P 的 next 引用指向结点 S，则 P 就是 S 的直接前驱，S 是 P 的下一个节点。单链表的一个重要特性就是只能通过前驱结点找到下一个结点，而无法从后续结点找到前驱结点。
二、单链表的查询、添加、修改、删除操作
【1】查询操作：在单链表中进行查找操作，只能从链表的首结点开始，通过每个结点的 next 引用来一次访问链表中的每个结点以完成相应的查找操作。例如需要在单链表中查找是否包含某个数据元素 e，则方法是使用一个循环变量 p，起始时从单链表的头结点开始，每次循环判断 p所指结点的数据域是否和 e 相同，如果相同则可以返回 true，否则让p指向下一个节点，继续循环直到链表中所有结点均被访问，此时 p 为 null；后续代码会实现。 关键操作：① 起始条件：p = head；② 结束条件：找到（e.equals(p.getData())==true）未找到（ p == null）③ p指向下一个结点：p = p.getNext()； 缺点：逐个比较，频繁移动指针，导致效率低下；
【2】修改操作：在单链表中修改数据，属于增删改查中最简单的操作，通过传入需要修改的节点对象，从链表的 head节点向下遍历，如果修改的节点编号NO等于链表中的某个编号NO则将链表中的节点修改为传入的节点即可。后续代码会实现。
【3】添加操作：在单链表中数据元素的插入，是通过在链表中插入数据元素所属的结点来完成的。对于链表的不同位置，插入的过程会有细微的差别。中间、末尾的添加过程其实是一样的，关键是在首部添加，会有不同，会改变整个单链表的起始结点。后续代码会实现。 关键操作：以添加中间结点为例：① 指明新结点的后继 s.setNext(p.getNext())；或者 s.next = p.next；② 指明新结点的前驱（其实是指明前驱结点的后继是新结点） p.setNext(s)；或者 p.next = s； 优缺点：添加节点不需要移动元素，只需要修改元素的指针即可，效率高。但是如果需要先查询到添加位置再添加新元素，因为有逐个查询的过程，效率不高。
【4】删除操作：类似添加操作，创建一个临时节点（temp）向下遍历，判断其 next节点是否等于需要删除的节点。如果等于则将临时的next节点指向 next节点的next节点。此时需要删除的节点就没有对象引用，JVM进行垃圾回收GC的时候则会回收此对象。后续代码会实现。
在使用单链表实现线性表的时候，为了使程序更加简洁，我们通常在单链表的最前面添加一个哑元结点，也称为头结点。在头结点中不存储任何实质的数据对象，其 next 域指向线性表中 0 号元素所在的结点，可以对空表、非空表的情况以及对首元结点进行统一处理，编程更方便，常用头结点。一个带头结点的单链表实现线性表的结构图如图所示：
三、单链表代码实例
package com.algorithms;
/**
* 模拟单链表
*/
public class SingleLinkedList {
//创建一个 head节点
Node head = new Node(0,"");
//向链表中添加元素,首先根据 no(模拟数组下标） 判断插入的位置
public void insert(Node n) throws IllegalAccessException {
//定义一个临时节点 插入、删除时使用
Node temp = head;
if(n == null || n.getNo() < 0){
throw new IllegalAccessException("传入的参数不合法");
}
//先判断插入的节点，链表中是否存在
Node node = get(n.getNo());
if(node != null){
System.out.println("该节点链表中已存在，不能插入");
return;
}
//如果当前节点等于null 或者 小于 temp.next 的no说明插入在temp.next前面，temp的后面
//因为是单链表，所以需要确定插入节点的前一个节点 temp 位置
while(true){
if(temp.getNext() ==null || n.getNo() < temp.getNext().getNo()){
//第一步：现将temp的next复制给新的节点
n.setNext(temp.getNext());
//第二步：将temp的next 变量更改为新插入的节点
temp.setNext(n);
break;
}else{
temp = temp.getNext();
}
}
}
//向链表中查询元素
public Node get(int index) throws IllegalAccessException {
//定义一个临时节点 插入、删除时使用
Node temp = head;
if(index < 0){
throw new IllegalAccessException("传入的参数不合法");
}
while(true){
if(temp.getNext() == null){
System.out.println("链表中不存在no="+index+"的元素");
return null;
}
if(temp.getNext().getNo() == index){
return temp.getNext();
}else{
temp = temp.getNext();
}
}
}
//修改节点 只能修改内容
public void update(Node n) throws IllegalAccessException {
//定义一个临时节点 插入、删除时使用
Node temp = head;
if(n == null){
throw new IllegalAccessException("传入的参数不合法");
}
while (true){
if(temp.getNext().getNo() == n.getNo()){
System.out.println("修改元素成功");
temp.getNext().setValue(n.getValue());
break;
}else{
temp = temp.getNext();
}
if(temp.getNext() == null){
System.out.println("链表中不存在的元素");
break;
}
}
}
//删除节点,根据下标删除，根据节点的话其实也是获取下标相同的来删除
public void remove(int index) throws IllegalAccessException {
//定义一个临时节点 插入、删除时使用
Node temp = head;
if(index < 0){
throw new IllegalAccessException("传入的参数不合法");
}
if(get(index) == null){
System.out.println("删除的节点链表中不存在");
return;
}
//判断temp的下一个节点是否等于当前节点
while(true){
if(temp.getNext().getNo() == index){
//将Next 的指针移动到下一位
temp.setNext(temp.getNext().getNext());
break;
}else{
temp = temp.getNext();
}
if(temp.getNext() == null){
System.out.println("删除的节点链表中不存在");
break;
}
}
}
//查看链表中的信息
public void list(){
//定义一个临时节点 插入、删除时使用
Node temp = head;
while (temp.getNext() != null){
System.out.println(temp.getNext().toString());
temp = temp.getNext();
}
}
//测试代码
public static void main (String[] args) throws Exception {
SingleLinkedList singleLinkedList = new SingleLinkedList();
Node first = new Node(1, "First");
Node second = new Node(2, "Second");
Node fourth = new Node(4, "Fourth");
//添加
singleLinkedList.insert(first);
singleLinkedList.insert(second);
singleLinkedList.insert(fourth);
//展示
singleLinkedList.list();
//向链表中添加元素
Node third = new Node(3, "Third");
singleLinkedList.insert(third);
//展示
/* 如下，有序
Node{no=1, value='First'}
Node{no=2, value='Second'}
Node{no=3, value='Third'}
Node{no=4, value='Fourth'}
*/
singleLinkedList.list();
//插入相同元素
//输出：该节点链表中已存在，不能插入
singleLinkedList.insert(third);
//修改节点
third = new Node(3, "Third--update");
singleLinkedList.update(third);
//输出：Node{no=3, value='Third--update'}
singleLinkedList.list();
//删除节点
singleLinkedList.remove(3);
singleLinkedList.list();
//获取 3 和 4
Node node3 = singleLinkedList.get(3);
Node node4 = singleLinkedList.get(4);
/* 输出
null
Node{no=4, value='Fourth'}
*/
System.out.println(node3);
System.out.println(node4);
}
}
class Node{
//编号，排序的属性，唯一
private int no;
private String value;
//单链表的特点，指向下一个与自己相同的对象
private Node next;
public Node(int no,String value){
this.no=no;
this.value = value;
}
public int getNo() {
return no;
}
public Node getNext() {
return next;
}
public void setNext(Node next) {
this.next = next;
}
public void setValue(String value) {
this.value = value;
}
public String getValue() {
return value;
}
@Override
public String toString() {
return "Node{" +
"no=" + no +
", value='" + value + '\'' +
'}';
}
}四、双向链表
单向链表的缺点：【1】单向链表，查找的方向只能是一个方向，而双向链表可以向前或者向后查找。 【2】单向链表不能自我删除，需要靠辅助节点 ，而双向链表，则可以自我删除，所以前面我们单链表删除时节点，总是找到temp，temp是待删除节点的前一 个节点； 与单向链表的区别：主要却别就是双向列表多了一个向前的指针 pre，能够通过当前节点，查看自己的上一个节点。方法的实现与单链表基本相同，就是由原来的只考虑 next 节点的情况，改变成了需要考虑 next 和 pre 两个节点而已；