链表

链表（linked list）,由一系列结点node（链表中每一个元素称为结点）组成，结点可以在运行时 i 动态生成

数据域： 存储数据的元素 指针域： 存储下个节点的地址

单向链表

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

Main ：（执行类）

public class Main {
    public static void main(String[] args) {
        
        //实例 操作对象
        MyLink myLink = new MyLink();
        
        //初始化链表数据
        // 参数： name ， id
        Node[] staff = {
                new Node(121,"小爱" , "00001"),
                new Node(112,"可怡"  , "00023"),
                new Node(233,"小黑" , "33123")
        };
        
        //添加链表
        for(Node tmp : staff){
            myLink.addLast(tmp);
        }
        
        //添加单链 （最后）
        myLink.addLast(new Node(232 , "智乃" ,"44221"));
        
        //插入单链（索引）  在 "可怡" 节点 链后添加 "黑猫" 节点
        myLink.addByValue(112 , new Node(234,"黑猫" , "00444"));
        
        // 节点值为121  "可怡" 删除
        myLink.removeNode(112);
        
        //查询数据
        System.out.println("查询节点值 234 的数据 ： ["+myLink.getNode(234)+"]");
        
        // 遍历链表
        System.out.println("=================");
        for (Node tmp : myLink.getNodeAll()){
            System.out.println(tmp.toString());
        }
        System.out.println("=================");
        
    }
}

Node ：（单链节点类）

/**
 * 单列节点
 * 链表中的节点，
 * data   代表节点的值
 * next   指向下一个节点的引用
 * @author Administrator
 */
public class Node {
    
    /**数据域 （员工数据）
     * name - 姓名
     * id - ID号
     * */
    String name;
    String id;
    
    /**指针域 （链表数据）
     * data - 节点的对象，即内容
     * next - 节点的引用
     */
    int data;
    Node next = null;
    
    //构造方法
    
    public Node() {
    }
    
    public Node(int data) {
        this.data = data;
    }
    
    public Node(int data , Node next) {
        this.data = data;
        this.next = next;
    }
    
    public Node(String name , String id) {
        this.name = name;
        this.id = id;
    }
    
    public Node(int data , String name , String id) {
        this.data = data;
        this.name = name;
        this.id = id;
    }
    
    public Node(int data , Node next , String name , String id ) {
        this.name = name;
        this.id = id;
        this.data = data;
        this.next = next;
    }
    
    public void setName(String name) {
        this.name = name;
    }
    public void setId(String id) {
        this.id = id;
    }
    
    @Override
    public String toString() {
        return "Node{" +
                "name='" + name + '\'' +
                ", id='" + id + '\'' +
                ", data=" + data +
                // ", next=" + next +
                '}';
    }
    
}

MyLink ：（链表操作类）

public class MyLink {
    //头节点
    Node head = null;
    
    /**
     * 链表尾部添加节点
     * @param d 节点值
     * @return 是否成功
     */
    public boolean addLast(int d){
        //实例节点
        Node newNode = new Node(d);
        //第一次创建的链头
        if (head == null){
            head = newNode;
            return true;
        }
        Node tmp = head;
        //遍历链表 循环直到最后 Node.next = null 空的节点引用
        while (tmp.next != null){
            //往后移一个节点，指向下一个节点
            tmp = tmp.next;
        }
        //在最后面null节点添加新节点
        tmp.next = newNode;
        return true;
    }
    
    /**
     * 链表尾部添加节点
     * @param node 节点对象
     * @return 是否成功
     */
    public boolean addLast(Node node){
        //第一次创建的链头
        if (head == null){
            head = node;
            return false;
        }
        Node tmp = head;
        //遍历链表 循环直到最后 Node.next = null 空的节点引用
        while (tmp.next != null){
            //往后移一个节点，指向下一个节点
            tmp = tmp.next;
        }
        //在最后面null节点添加新节点
        tmp.next = node;
        return true;
    }
    
    /**
     *  指定值 后面添加节点
     * @param value 节点值
     * @param node 单节点
     */
    public boolean addByValue(int value , Node node){
        Node tmp = head;
        //第一次添加则无效
        if (tmp == null){
            return false;
        }
        //遍历链表
        while(tmp != null){
            //data 节点内容 相同为止
            if(tmp.data == value){
                //插入
                //更改指向
                node.next = tmp.next;
                //节点的下一位
                tmp.next = node;
                return true;
            }
            //指向下一节点
            tmp = tmp.next;
        }
        return false;
    }
    
    /**
     *  删除节点
     * @param value
     * @return 是否成功
     */
    public boolean removeNode(int value){
        if (head == null){
            return false;
        }
        //如果要删除头 ，将头的下一个覆盖即可
        if (head.data == value){
            head = head.next;
            return true;
        }
        Node tmp = head;
        //遍历链表
        while (tmp.next != null){
            if (tmp.next.data == value){
                //该节点被 上节点连接至 下下节点
                tmp.next = tmp.next.next;
                return true;
            }
            tmp = tmp.next;
        }
        return false;
    }
    
    /**
     * 获取指定节点
     * @param value
     * @return
     */
    public Node getNode(int value){
        if (head.data == value){
            return head;
        }
        Node tmp = head;
        while (tmp != null){
            if (tmp.data == value){
                return tmp;
            }
            tmp = tmp.next;
        }
        return null;
    }
    
    /**
     * 获取链表全部
     * @return
     */
    public Node[] getNodeAll(){
        if (head == null){
            return null;
        }
        Node tmp = head;
        Node[] arrayNode = new Node[size()];
        int i = 0;
        while (tmp != null){
            arrayNode[i++] = tmp;
            tmp = tmp.next;
        }
        return arrayNode;
    }
    
    /**
     * 获取链表长
     * @return
     */
    public int size(){
        Node tmp  = head;
        int size = 0;
        while (tmp != null){
            size++;
            tmp = tmp.next;
        }
        return size;
    }
    
    /**
     * 是否为空
     * @return
     */
    public boolean isEmpty(){
        return head == null;
    }
    
    /**
     *  获取 头节点
     * @return
     */
    public Node getHead(){
        return head;
    }
    
    /**
     * 获取 尾节点
     * @return
     */
    public Node getTail(){
        if (head == null){
            return head;
        }
        Node tmp = head;
        while (tmp.next != null){
            tmp = tmp.next;
        }
        return tmp;
    }
}

学习来源分享链接：点击 (opens new window)

双向链表

由各个内存结构通过指针 Next 和指针 Prev 链接在一 起组成，每一个内存结构都存在前驱内存结构和后继内存结构(链头没有前驱，链尾没有后继），内存结构由数据域、指针域 （Prev , Next）组成

详细图解

Main 执行类：

public class Main {
    public static void main(String[] args) {
        
        MyLink myLink = new MyLink();

        Node[] staff = {
                new Node(111 ,1),
                new Node(222 , 2),
                new Node(444 , 4),
        };
        
        for (Node tmp : staff){
            myLink.addLast(tmp);
        }
        //添加节点值
        myLink.addLast(555);
        
        //插入链表 指定 date 222 后面添加 节点值 333
        myLink.addByValue(222 , new Node(333,3));
        
        //删除链表 指定 date 222 删除
        myLink.removeNode(222);

        /*以下是打印操作 ， 可以自定选择
        	打印形式可更改 Node类 中的 toString方法 进行打印
        */
	
        System.out.println(myLink.getByNode(555));
        System.out.println();
       
        //System.out.println(myLink.getTail().getPrev());
        System.out.println(myLink.getHead());
        System.out.println("===============");
        System.out.println(myLink.getTail());
        //System.out.println(myLink.getHead().getNext());

        System.out.println();
        System.out.println("size = "+ myLink.size());
        
    }
}

MyLink 操作类：

public class MyLink {
    
    Node head = null;
    
    /**
     * 添加链表（节点值）
     * @param d
     */
    public void addLast(int d){
        Node newNode = new Node(d);
        if (head == null){
            head = newNode;
            return;
        }
        Node tmp  = head;
        while (tmp.next != null){
            tmp = tmp.next;
        }
        tmp.next = newNode;
        //指向后面
        newNode.prev = tmp;
    }
    
    /**
     * 添加链表（节点）
     * @param node
     */
    public void addLast(Node node){
        if (head == null){
            head = node;
            return;
        }
        Node tmp  = head;
        while (tmp.next != null){
            tmp = tmp.next;
        }
        tmp.next = node;
        node.prev = tmp;
    }
    
    /**
     * 插入节点
     * 指定节点值 value 的后面添加 节点
     * @param value
     * @param node
     * @return
     */
    public boolean addByValue(int value , Node node){
        if (head == null){
            return false;
        }
        Node tmp = head;
        while (tmp != null){
            if (tmp.date ==value){
                //反向链 处理
                tmp.next.prev = node;
                node.prev = tmp;
                
                node.next = tmp.next;
                tmp.next = node;
                return true;
            }
            tmp = tmp.next;
        }
        return false;
    }
    
    /**
     * 删除指定节点
     * @return
     */
    public boolean removeNode(int value){
        if (size() == 0 || head == null){
            return false;
        }
        Node tmp = head;
        while (tmp.next != null){
            if (tmp.next.date == value){
                tmp.next.next.prev = tmp;
                //next 跳过指向
                tmp.next = tmp.next.next;
                return true;
            }
            tmp = tmp.next;
        }
        return false;
    }
    
    /**
     * 获取链表长
     * @return
     */
    public int size(){
        Node tmp = head;
        int size = 0;
        while (tmp != null){
            size++;
            tmp = tmp.next;
        }
        return size;
    }
    
    /**
     * 获取 指定节点
     * @param date
     * @return
     */
    public Node getByNode(int date){
        Node tmp = head;
        while (tmp != null){
            if (tmp.date == date){
                return tmp;
            }
            tmp = tmp.next;
        }
        return null;
    }
    
    /**
     *  获取 头节点
     * @return
     */
    public Node getHead(){
        return head;
    }
    
    /**
     * 获取 尾节点
     * @return
     */
    public Node getTail(){
        if (head == null){
            return head;
        }
        Node tmp = head;
        while (tmp.next != null){
            tmp = tmp.next;
        }
        return tmp;
    }
}

Node 单链类：

import java.util.Objects;

public class Node {
    
    //数据域 （内容自定义）
    String name;
    int id;
    
    /**指针域
     *  date - 节点值（数据类型自定义）
     *  prev - 节头 引用
     *  next - 节尾 引用
     */
    int date;
    Node prev;
    Node next;
    
    
    public Node(int date) {
        this.date = date;
    }
    
    public Node(int date, Node prev, Node next) {
        this.date = date;
        this.prev = prev;
        this.next = next;
    }
    
    public Node(String name, int id, int date, Node prev, Node next) {
        this.name = name;
        this.id = id;
        this.date = date;
        this.prev = prev;
        this.next = next;
    }
    
    public Node(int date , int id) {
        this.id = id;
        this.date = date;
    }
    
    public boolean equals(int d) {
        return date == d;
    }
    
    //输出属性 next 或 prev 二选一
    @Override
    public String toString() {
        return "Node{" +
                //"id=" + id +
                "date=" + date +
                //", next= "+next+
                ", prev="+prev+
                '}';
    }
    
    @Override
    public int hashCode() {
        return Objects.hash(date);
    }
}

循环链表

循环链表没有链头和链尾的说法，因为是闭环的，所以每一个内存结构都可以充当链头 和链尾

单向循环链表

由各个内存结构通过一个指针 Next 链接在一起组成，每一个内存结构都存在后继内存结构，内存结构由数据域和 Next 指针域组成

链尾的 Next 指针直接指向链头，形成一个闭环

双向循环链表

由各个内存结构通过指针 Next 和指针 Prev 链接在一起组成，每一个内存结构都存在前驱内存结构和后继内存结构，内存结构由 数据域、Prev 指针域和 Next 指针域组成

链尾的 Next 指针指向链头，再把链头的 Prev 指针指向链尾，形成一个闭环

闭环我就不多写了，头尾连接即可