一、链表

1、什么是链表

链表 [Linked List]：链表是由一组不必相连（不必相连：可以连续也可以不连续）的内
存结构（节点），按特定的顺序链接在一起的抽象数据类型。

补充： 抽象数据类型（Abstract Data Type [ADT]）：表示数学中抽象出来的一些操作的集合。
内存结构：内存中的结构，如：struct、特殊内存块…等等之类；

数组和链表的区别和优缺点：
数组是一种连续存储线性结构，元素类型相同，大小相等
数组的优点：
存取速度快
数组的缺点：
事先必须知道数组的长度
插入删除元素很慢
空间通常是有限制的
需要大块连续的内存块
插入删除元素的效率很低

链表是离散存储线性结构
n 个节点离散分配，彼此通过指针相连，每个节点只有一个前驱节点，每个节点只有一 个后续节点，首节点没有前驱节点，尾节点没有后续节点。
链表优点： 空间没有限制 插入删除元素很快
链表缺点： 存取速度很慢

2、链表共分几类？

链表常用的有 3 类： 单链表、双向链表、循环链表。
链表的核心操作集有 3 种：插入、删除、查找(遍历）

1、单链表

单链表 [Linked List]：由各个内存结构通过一个 Next 指针链接在一起组成，每一个内
存结构都存在后继内存结构(链尾除外），内存结构由数据域和 Next 指针域组成。

单链表实现图示：

解析： Data 数据 + Next 指针，组成一个单链表的内存结构 ； 第一个内存结构称为 链头，最后一个内存结构称为 链尾； 链尾的
Next 指针设置为 NULL [指向空]； 单链表的遍历方向单一（只能从链头一直遍历到链尾）

单链表操作集：

2、双向链表

双向链表 [Double Linked List]：由各个内存结构通过指针 Next 和指针 Prev 链接在一
起组成，每一个内存结构都存在前驱内存结构和后继内存结构(链头没有前驱，链尾没有后 继），内存结构由数据域、Prev 指针域和 Next
指针域组成。

双向链表实现图示：

解析： Data 数据 + Next 指针 + Prev 指针，组成一个双向链表的内存结构； 第一个内存结构称为 链头，最后一个内存结构称为
链尾； 链头的 Prev 指针设置为 NULL， 链尾的 Next 指针设置为 NULL； Prev 指向的内存结构称为 前驱， Next
指向的内存结构称为 后继； 双向链表的遍历是双向的，即如果把从链头的 Next 一直到链尾的[NULL] 遍历方向定 义为正向，那么从链尾的
Prev 一直到链头 [NULL ]遍历方向就是反向；

双向链表操作集：

3、循环链表

单向循环链表 [Circular Linked List] : 由各个内存结构通过一个指针 Next 链接在一起
组成，每一个内存结构都存在后继内存结构，内存结构由数据域和 Next 指针域组成。 双向循环链表 [Double Circular
Linked List] : 由各个内存结构通过指针 Next 和指针 Prev
链接在一起组成，每一个内存结构都存在前驱内存结构和后继内存结构，内存结构由 数据域、Prev 指针域和 Next 指针域组成。

循环链表的单向与双向实现图示：

解析： 循环链表分为单向、双向两种； 单向的实现就是在单链表的基础上，把链尾的 Next 指针直接指向链头，形成一个闭环；
双向的实现就是在双向链表的基础上，把链尾的 Next 指针指向链头，再把链头的 Prev 指针指向链尾，形成一个闭环；
循环链表没有链头和链尾的说法，因为是闭环的，所以每一个内存结构都可以充当链头 和链尾；

循环链表操作集：

链表简介

使用JAVA做可爱得小单向链表，通过上线去找下线，上线莫名死了就完了，下线失联了，对下线得操作都要通过上线
1.使用类创造一个节点
2.建立一个头节点，头节点得地址就是整个链表得地址

JAVA中一个基本的链表节点就是这样的

public class HeroNode {//用类来做节点，一个节点就做完了
    public int age;
    public String name;
    public String nickName;

    public HeroNode next;//使用类做指针，指向下一个

    @Override
    public String toString() {//为了显示方便重写toString方法
        return "HeroNode{" +
                "age=" + age +
                ", name='" + name + '\'' +
                ", nickName='" + nickName + '\'' +
                '}';
    }

    public HeroNode(){//一个无参构造

    }
    public HeroNode(int age, String name, String nickName){//一个构造器
        this.age = age;
        this.name = name;
        this.nickName = nickName;

    }
}

链表的内容和操作

public class SingleLInkedList {
    private HeroNode headNode = new HeroNode();//头节点,头节点相当于变量地址

    /*
    <整理资料>
Q：什么是头结点？
A：数据结构中，在单链表的开始结点之前附设一个类型相同的结点，称之为头结点。头结点的数据域可以不存储任何信息，
头结点的指针域存储指向开始结点的指针（即第一个元素结点的存储位置）。
A：头结点其实就是一个数据域为空的结点（当然也可储存链表的长度之类的数据，一般对链表操作无影响），
而首元结点就是第一个元素结点，即头结点后边的第一个结点。

Q：用来干嘛？
A：
1、防止单链表是空的而设的。当链表为空的时候,带头结点的头指针就指向头结点。如果当链表为空的时候,
单链表没有带头结点,那么它的头指针就为NULL。
2、在第一个元素结点前插入结点（或删除第一个结点），使其操作与对其它结点一致。带头结点时，
不论删除哪个位置上的结点，用到的代码都一样；不带头结点时，删除第1个元素和删除其它位置上的元素用到的代码不同，
相对比较麻烦。
     */

    public HeroNode getHeadNode() {
        return headNode;
    }

    public void delete(int age){//删除节点，找到前一个节点
        //根据年龄删除人
        //辅助节点
        HeroNode temp = headNode;
        boolean flag = false;//判断有没有找到
        while(true){
            if(temp.next == null){
                break;
            }

            if(temp.next.age == age){//找到位置了
                flag = true;
                break;

            }

            temp = temp.next;//没找到就继续往下走
        }

        if(flag){
            temp.next = temp.next.next;
        }
        else
            System.out.println("我们没找到");

    }

    //添加节点到单向列表
    //找到当前链表，最后一个节点
    //将next指向最后一个节点
    public void add(HeroNode heroNode){
        HeroNode temp = headNode;//一个头指针
        while(true){//从头指针开始遍历
            if(temp.next == null ){
                break;
            }

            else
                temp = temp.next;
            //由于没有尾指针的概念，所以JAVA中链表，都是从头开始遍历，去找尾指针的
        }

        //将尾指针和后面连接起来
        temp.next = heroNode;

    }

    public void show(){//显示链表
        //需要辅助变量来遍历整个链表
        //先判断链表是否为空
        if(headNode == null){
            System.out.println("链表为空你个傻逼");

        }

        else{
            HeroNode temp = headNode.next;//从头节点的尾巴开始遍历
            while(temp != null){
                System.out.println(temp);//这里已经重写了toString方法
                temp = temp.next;//指针后移
            }
        }

    }

    /*
    添加一个变量进来，先找到变量添加位置的前一个节点，
    断开添加位置的连接
    然后插入完成
     */
    public void insert(HeroNode heroNode){
        HeroNode temp = headNode;
        while(true){//寻找插入的位置
            if(temp.next == null){
                break;
            }

            if (temp.next.age > heroNode.age){//位置找到了，找到正确添加排名的位置了
                break;//

            }
            else if(temp.next.age == heroNode.age){//说明要插入的位置查重复了
                System.out.println("你插入重复了");
                break;
            }

            temp = temp.next;
        }

        heroNode.next = temp.next;//给插上，先把尾巴接好，再去接头，接头接活过来了
        temp.next = heroNode;

    }

    //根据年龄来对人物进行姓名和昵称的修改，对链表进行增删改查

    public void update(HeroNode newHeroNode){
        if(headNode.next == null){//先进行判空
            System.out.println("链表为空");
            return;

        }

        HeroNode temp = headNode;//熟悉的从头节点开始遍历的环节
        //按照年龄找到需要修改的节点
        boolean flag = false;
        while(true){
            if(temp == null){
                break;//到链表的最后啦，我没找到

            }
            if (newHeroNode.age == newHeroNode.age){
                flag = true;//这个要放在break之前,说明我找到了，而不是没找到

                break;           //说明你找到

            }

        }
        if(flag){
            temp.name = newHeroNode.name;
            temp.nickName = newHeroNode.nickName;
        }
        else
            System.out.println("没有找到这个编号，你是不是傻了");

    }


}

面试题目

public class TencentGroup {
    //面试第一题，求单链表的有效节点个数
    public static int length(HeroNode headNode){//把头节点当地址传递进来
        if(headNode.next == null){
            System.out.println("这是空的单链表");
            return 0;
        }
        int length = 0;
        HeroNode temp = headNode.next;//辅助节点进行遍历,头节点不算，从第二个开始
        while(true){
            if(temp == null){

                break;
            }

            else{
                length ++;
            }
            temp = temp.next;
        }
        return length;
    }

    /*
    查找倒数第k个节点
     */
    public static HeroNode findKNode(int index,HeroNode headNode){//index查找倒数第几个节点
        /*
        先从头到尾遍历链表，得到链表总的长度，得到链表的有效节点后
        从链表的头开始遍历
        遍历到第n - k个节点
         */
            if (headNode.next == null){
                return null;
            }
            int length = TencentGroup.length(headNode);//直接调用写好了方法得到链表有效节点上个数

            //先做一个Index的检验
            if(index <= 0 || index > length){
                System.out.println("目录有问题");
            }
            HeroNode temp = headNode.next;//用于去遍历

           for (int i = 1; i <= length - index;i++ ){
                if(temp == null){//遍历到头的话，跳出遍历
                    break;
                }
                temp = temp.next;
                //一直找到倒数第k个节点

            }
           return temp;//将找到的节点返回去

        }

    }

 /*
   将链表反转
   链表只能通过上面找下面
   上线找下线
   遍历链表
   将遍历到的节点放在，新的头节点上，然后用头插法，把后面节点插上去
   完成链表的改造
     */

如图所示

单链表只能从上线找下线，下线没办法找上线
因此，遍历链表，采用头插法，将链表颠倒后放在新的头结点上

 public HeroNode  reversetList(HeroNode headNode){
        System.out.println("传进来的地址是" + headNode);



        /*
        若只有一个节点直接返回
         */
        if(headNode.next == null){
            System.out.println("你个傻逼，没有");

        }
        else{
            HeroNode temp = headNode.next;
            HeroNode cur  = null;//需要两个链表来控制移动节点
            //一个移动上线，另一个保存下线，不然上线没了，下线找不到了
            do{

                cur = temp.next;//先保存，然后判断
                //cur保存temp的下一个节点

                temp.next = newHeadNode.next;//断开连接，头插法先把尾巴连接好
                newHeadNode.next = temp;//与新的头节点连接上
                temp = cur;//头指针移动去找下一个节




            }
            while(temp != null);
            headNode.next = null;//最后让headNode链表归于平静


        }
        System.out.println("新头地址是" + newHeadNode);

        return newHeadNode;





    }

*我自己写的！有头节点尾节点！*没有头尾节点我要吐了
JAVA中没有指针的概念，只有引用数据类型，所以我们使用一个节点，充当指针得作用，毕竟new出来的都在堆里，你的节点名字也只是指向它而已

自己创造的链表节点部分：
1.注意让创造出来的指针域默认为Null比较方便操作

package linkedList;

public class Node {
    public int age;
    public String name;
    public String nickName;
    public Node nextNode = null;//默认是等于null的

    public Node(int age, String name, String nickName, Node nextNode) {
        this.age = age;
        this.name = name;
        this.nickName = nickName;
        this.nextNode = nextNode;
    }

    public Node() {
    }

    @Override
    public String toString() {
        return "Node{" +
                "age=" + age +
                ", name='" + name + '\'' +
                ", nickName='" + nickName + '\'' +

                '}';
    }
}

代码主题部分，增加了头节点和尾节点，方便操作：

1.尾插法，在尾指针后面插入数据
使用尾巴指针插入新的节点，并且让尾指针指向最后一个节点

  public void add(int age,String name,String nickName) {//一个被发展的新下线
        //追加节点
        //使用尾指针进行追加节点，
        headNode.age++;//使用头节点在存放链表长度

        Node newNode = new Node();//先开辟一块空间，批一块地
        //完成数值输入
        newNode.age = age;
        newNode.name = name;
        newNode.nickName = nickName;
        //想要新加入和上游生态连接上
        tailPoint.nextNode = newNode;
        tailPoint = newNode;//加入传销组织自己成为其中的一员
        tailPoint.nextNode = null;//强调一下尾节点的next为null的问题

    }

2.打印整个链表

1. 一个临时指针从头开始
2. 打印一个移动一次
3. 直到打印到链表尾部

 //遍历一下整个链表玩一玩
    public void show(){
        //先判断一下链表是不是空的
        if(headNode.nextNode == null){
            System.out.println("链表为空");
        }
        else{
            Node temp = headPoint.nextNode;//从头节点的下一个节点
            //利用一个临时节点从头开始遍历
            while(temp != null){//相当于遍历到最后一个节点了
                System.out.println(temp);//我已经改写toString方法了
                temp = temp.nextNode;//指针后移
            }

        }
    }

整个链表代码
真的难点在于链表删除的位置：
1.遍历到链表的要删除节点的前一个节点位置
2.完成上下连接
3.注意判断条件是temp.next.age == 条件，用前面一个节点，表示下一个节点
4.注意temp要从head开始，不然首节点判断不到
5.结束时候temp不要到最后一个节点才结束，因为尾巴指针已经被判断过了，
6.尾巴指针对应的节点很可能一开始就被删除了，注意
7.删除一个节点很容易，这个节点将下面交给上级就行了

package linkedList;

import com.sun.corba.se.impl.orb.ParserTable;

import java.sql.SQLOutput;

public class LinkedList {
    private Node headNode = new Node();//建立一个头节点
    //头节点代表整个链表的位置，比如某些时候用一个师长位置代表一个师
    private Node headPoint =  headNode;//头指针
    private Node tailPoint = headPoint;//尾指针
    //尾巴节点的next应该是为null的，我这里，所有新new的节点Node中next全部都是默认为null的


    public LinkedList() {
        this.headNode.age = 0;//给头节点中age设置初始值为0，用来存放链表长度

    }

    public int size(){
        return this.headNode.age;//将头节点里age返回回去统计长度
    }


    public Node getHeadNode() {//将链表头节点返回回去
        return headNode;
    }



    //这是尾插法

    public void add(int age,String name,String nickName) {//一个被发展的新下线
        //追加节点
        //使用尾指针进行追加节点，
        headNode.age++;//使用头节点在存放链表长度

        Node newNode = new Node();//先开辟一块空间，批一块地
        //完成数值输入
        newNode.age = age;
        newNode.name = name;
        newNode.nickName = nickName;
        //想要新加入和上游生态连接上
        tailPoint.nextNode = newNode;
        tailPoint = newNode;//加入传销组织自己成为其中的一员
        tailPoint.nextNode = null;//强调一下尾节点的next为null的问题

    }

    //遍历一下整个链表玩一玩
    public void show(){
        //先判断一下链表是不是空的
        if(headNode.nextNode == null){
            System.out.println("链表为空");
        }
        else{
            Node temp = headPoint.nextNode;//从头节点的下一个节点
            //利用一个临时节点从头开始遍历
            while(temp != null){//相当于遍历到最后一个节点了
                System.out.println(temp);//我已经改写toString方法了
                temp = temp.nextNode;//指针后移
            }

        }
    }

 //删除所有拥有同一数字的链表
    public void deleteAll(int number){
//删除链表时候，要用到前一个节点去删除后一个节点，所以一定要从头节点开始遍历，不然没办法处理首节点
        Node temp = headPoint;//创造出来一个遍历用的临时节点
        boolean flag = false;//用来判断一下有没有找到节点

        if(headNode.nextNode == null){//判空
            System.out.println("链表为空");
        }
        else {
            while (temp.nextNode != null){//无论如何都要将链表从头到尾都去看一下，将所有对上的节点都删除了
                if(temp.nextNode.age == number){
                    this.headNode.age --;//先链表长度减一
                    flag = true;//找到了
                    temp.nextNode = temp.nextNode.nextNode;//上下线完成连接
                }

                temp = temp.nextNode;//链表移动
                if(temp == null){//如果循环到达结尾跳出循环
                    break;
                }

            }

            if(flag == false){
                System.out.println("不存在这样的节点");
            }

            if(headNode.age == 0){
                tailPoint = null;//元素被删完了，就让尾指针回去
            }

        }


    }


//删除摸某一节点，以age去找到这个节点
    public void delete(int number){
        //由于每次需要使用的都是用前一个节点去判断下面那个节点符合不符合规定
        //所以必须从头节点开始赋值，不然第一个节点不会被覆盖到
        if(headNode.nextNode == null){
            System.out.println("链表是空的");
        }
        else{
            Node temp = headPoint;//一个指针从头开始找这个节点
            boolean flag = false;//设置一个标志位，找到了的话，标志位为true

            //删除节点，需要找被删除节点上一个节点，除掉下线，用上线，借助上线除掉下线
            while (true){
//这里不要用尾指针进行判断，因为尾指针对应节点可能一开始就被删除
                if(temp.nextNode == null){//当连链表遍历到尾指针的位置就退出
                    //前一个节点的后一个节点进行判断，所以尾指针上的节点已经被判断过了
                    break;//遍历完了就退出
                }

                if(temp.nextNode.age == number){//找到了
                    headNode.age  = headNode.age - 1;//减去一个数量
                    flag = true;
                    //删除节点之后跳出循环
                    //先交代下线是谁
                    temp.nextNode = temp.nextNode.nextNode;//新的上下线连接成功
                    //旧的就被销毁了
                    break;//找到了就退出循环了
                }

                temp = temp.nextNode;//移动指针
            }

            //链表中不包含节点的处理
            if(flag == true){
                System.out.println("我们成功删除了链表");
            }
            else{
                System.out.println("链表中不包含这个节点");
            }

        }

        if(this.headNode.age == 0 ){
            tailPoint = headPoint;//当链表被删除干净时候，将尾指针指向头节点等待下一次使用
        }
    }


//插入新的节点，根据年龄插入节点
    public void insert(int pos,Node newNode){//插入位置，和插入的节点
        Node temp = new Node();
        temp = headPoint.nextNode;//开始遍历
        boolean flag = false;

        while(true){

            if(temp.age == pos){
                headNode.age = headNode.age + 1;//插入新节点了，链表长度增加

                flag = true;//找到了
                //完成插入
                //插新的节点，上线介绍认识下线，然后和上线建立练习
                newNode.nextNode = temp.nextNode;
                //然后和上线建立联系
                temp.nextNode = newNode;
                break;//插入完成后就跳出

            }

            temp = temp.nextNode;//指针后移
            if(temp == null){
                break;//到最后了，跳出去
            }


        }

        if(flag == false){
            System.out.println("没有插入位置");
        }

    }
    

}

自己很喜欢的一段代码

//找到某个点，插入这个点前面
    public boolean findOne(int no,String name){
        //也许能找到这个点，找不到就报false，并且将这个点尾巴插入，用
        //能找到的情况下，插入前头，找不到就尾巴插入
        Node temp = headNode;
        Node newNode = new Node(no,name);
        boolean find = false;//默认是找不到
        //找前面一个点

        while(temp.next != null){
            if(temp.next.no == no ){
                find = !find;
                break;//找到了就跳出去
            }

            temp = temp.next;//往后移动

        }


        //跳出来要么找到了，要么没找到
        //找到了就插入
        if(find){
            newNode.next = temp.next;
            temp.next = newNode;//连接上

        }

        //找不到就直接尾巴插入
        if(!find){
            addOne(no,name);
        }

        return find;//然后将find返回去，告诉计算机我们有没有找到
    }

链表是由值和地址组成，地址指向下一个值的地址，如下图所示

我们先定义一个节点类Listnode，里面包含值和地址属性，再通过构造器传值为这个值在内存中申请一块区域。代码如下：

public class Listnode {
    //链表中一个节点的值属性
	public int value;
//链表中一个节点的指针域属性，指向下一个值的地址，因为下一块区域是Listnode类型的所以next也是Listnode类型
	public Listnode next;
//构造器，通过值传递给value赋值
	public Listnode(int n) {
		this.value=n;
	}
	
}

先创建一个链表类Linklist.

头插法的思路是定义一个头指针Listnode head=null，把第一个节点的地址通过值传递给它，再创建节点时，让这个新节点的next指针指向旧节点，再让这个头指针指向新节点。如下图：

头插法看如下代码：

public void startAdd(int n) {
//通过new实例给value创建一个新节点
		Listnode listnode=new Listnode(n);
//让新节点的下一个指向旧节点，因为旧节点通过值传递的方式传给head
		listnode.next=head;
//新节点通过值传递的方式传给head
		head=listnode;
	}

尾插法的思路是先定义一个游标temp，游标从头结点head开始，如果它的next指针域不是null，就让游标指向下一个，直到游标指向next指针域为null，然后在这个节点后插入新的节点。

尾插法代码如下：

public void endAdd(int n) {
//通过new实例给value创建一个新节点
		Listnode listnode=new Listnode(n);
//判断头结点是否为空，空就通过值传递把新节点传给头节点，直接return不再走下面的流程
		if(head==null) {
			head=listnode;
			return;
		}
//定义游标
		Listnode temp=head;
//通过游标判断此节点的next指针域是否为空，不是就指向下一个节点
		while(temp.next!=null) {
			temp=temp.next;
		}
//此时指向最后一个节点，让它的next指针域指向新节点
		temp.next=listnode;
	}

总体代码如下：

public class Linklist {
//定义头指针
	Listnode head;
//头插法
	public void endAdd(int n) {
		Listnode listnode=new Listnode(n);
		if(head==null) {
			head=listnode;
			return;
		}
		Listnode temp=head;
		while(temp.next!=null) {
			temp=temp.next;
		}
		temp.next=listnode;
	}
//尾插法
	public void startAdd(int n) {
		Listnode listnode=new Listnode(n);
		listnode.next=head;
		head=listnode;
	}
//把添加的值打印的方法
	public void printLink() {
		Listnode temp=head;
		while(temp!=null) {
			System.out.print(temp.value+" ");
			temp=temp.next;
		}
	}
//获取添加多少数的方法
	public void getLength() {
		int count=0;
		if(head==null) {
			System.out.println(0);
			return;
		}
		Listnode temp=head;
		while(temp!=null) {
			count++;
			temp=temp.next;
		}
		System.out.println("你添加了"+count+"个数");
	}
}

通过test类来测试一下：

public class Test {
	public static void main(String[] args) {
		Linklist linklist=new Linklist();
		linklist.endAdd(1);
		linklist.endAdd(2);
		linklist.endAdd(3);
		linklist.endAdd(4);
		linklist.startAdd(2);
		linklist.startAdd(3);
		linklist.startAdd(4);
		linklist.printLink();
		linklist.getLength();
	}
}

结果如下：