节点 是数据结构的基础，是数据结构的基础 构成复杂数据结构的基本组成单位。

public class Node { 
          public long data;  public Node next;     public Node(long value) { 
           this.data = value;  }  } 

链表：

通常由一系列组成 节点 每个节点包含任何实例数据（data fields）一两个用来指向 上一个 或 下一个 链接节点的位置(links”）。

以上是单链表的存储原理图，head作为第一个节点，它不存储任何数据，只是指向链表中存储数据的第一个节点，每个节点都有一个 next 引用，指向下一个节点，一个接一个地记录下来，直到最后一个节点 next 指向 null 。

(1)普通链表(单链表): 单链表的节点类保留下一节点的引用。链表类只保留头节点的引用，只能从头节点插入删除 (想想为什么？；

(2)双端链表: 双端链表的节点类保留引用下一节点。链表类头节点和尾节点的引用可以从尾节点插入，但只能从头节点删除 (想想为什么？；

(3)双向链表: 双向链表的节点类保留引用上节点和下节点。链表类头节点和尾节点的引用可以从尾节点插入删除；

如图所示：

(4)无序链表 最大的特点是 增加头部或尾部 新节点。

上面几种 链表都是 无序链表。

（5）有序链表：

增加、减少或其他符合一定条件的规则，插入数据时，从头结点到每个节点，在符合规则的地方插入新节点。

普通链表 ，也叫 单链表 或者 单向链表。

链表是一种数据存储结构。Java原生JDK链表也相应实现。 单向链表是链表之一，其主要原理是：

• 链表以节点为基础（Node）要保存的数据以节点对象的形式存储。

• 下一个节点被引用到单向链表中的每个节点（Node next），下一个节点可以通过上一个节点依次串联找到，所以如果你想遍历整个单向链表，你需要找到第一个节点。

• **链表不同于数组，不一定是内存中的连续空间，**由于它是一个节点存储只需要持有下一个节点的地址，就可以利用内存中分散的空间进行保存。

• 很多人都知道链表比较相比List他添加和删除速度快，查询速度慢，主要是因为链表的修改只需要修改前持有的前节点和后节点的引用，而list删除或添加操作时，通常需要移动集合元素，因此需要很长时间。但是，事实上，如果不考虑随机插入，仍然需要根据实际情况进行判断，最后一直插入，list它非常快，因为不需要移动元素，但如果它是随机插入或插入在前面，链表有很大的优势，所以谁快谁慢或结合具体问题.

单链表 链表中最简单的结构。单链表的节点(Node)分为两部分，第一部分(data)保存或显示关于节点的信息，并将下一个节点的地址存储在另一部分。最后一个节点存储地址的部分指向空值。

• 查找：单向链表 只有一个方向，一般需要从第一个节点开始每次访问下一个节点，直到需要的位置。
• 插入：插入一个节点，对于单向链表，我们只提供插入链表头，只需将当前插入的节点设置为头节点，next指向原始节点。
• 删除：删除节点，我们将节点的最后一个节点next指向节点的下一个节点。

查找图：

在表头添加节点：

删除节点：

在JDK链表的集合容器已经包装在中间，我们可以直接使用，但手动实现一些基本功能仍然有助于更好地理解底层原理，加深对这种数据结构的理解。

• 要实现链表，首先需要定义节点。根据以上分析，单向链表中的节点应持有下一个节点的参考值和要存储的数据值。为了更好地通用，这里的数据层应该包装Object但是为了方便这里没有包装。

/*** * 节点 */
class Node{ 
        
    //************数据层************
    //可封装为Object
    public int no;
    public String name ;
    public String nick;
    //******************************
    //下一个节点的引用
    public Node next;

    public Node(int no , String name , String nick){ 
        
        this.no = no ;
        this.name = name ;
        this.nick = nick ;
    }

    @Override
    public String toString() { 
        
        return "Node{" +
                "no=" + no +
                ", name='" + name + '\'' +
                ", nick='" + nick + '\'' +
                '}';
    }
}

首先我们需要声明一个头结点Head,这个head不存放具体的数据,只是记录第一个节点的地址。

public class LinkedList { 
        
 //声明一个头结点.这个节点不放具体的数据,只记录第一个节点的地址
 //根据上面的Node的构造方法初始化,next指针先不赋值.
    private Node head = new Node(0 , "" , "");
}

• 思路分析
• 首先我们需要声明一个第三变量temp来作为指针,开始时默认指向头结点,添加新节点时循环遍历链表,每循环一次,temp就后移一位,找到链表的最后一个节点,找到最后一个节点之后只需将原来的最后一个节点的next指向新加节点即可,判断是否是最后一个节点的条件应该是temp的next值为null,这样新加的节点就变成了最后一个节点,这里需要保证新加节点的next值为null.

public class LinkedList { 
        
    //声明一个头结点.这个节点不放具体的数据,只记录第一个节点的地址
    private Node head = new Node(0 , "" , "");

    /** * 添加方法，这里的添加需要保证插入的Node是新的next是null,如果next的值不为空之前使用过指向另一个 * Node地址的话会出现添加一个却把之前链表都连起来的情况,如果恰巧形成了闭环,首尾相连会出现死循环的情况 * @param newNode * @return */
    public boolean add(Node newNode){ 
        
        //声明一个第三变量用作指针,开始默认指向头结点
        Node temp = head;
        //循环遍历链表,将新节点加入到next为null的节点后,就是直接加入到最后一个节点的后面
        while(true){ 
        
            //如果当前节点的下一个节点是null ,说明该节点是最后一个节点
            if(temp.next == null){ 
        
                //直接将新节点添加到最后一个节点之后,next指向新节点
                temp.next = newNode;
                return true;
            }
            //将指针后移一位,指针指向下一个节点
            temp = temp.next ;
        }
    }
}

• 这个只需要判断头结点的next是否为null即可

/** * 判断链表是否为空的方法 * @return */
    public boolean isEmpty(){ 
        
        //如果头结点的下一个是空,就说明链表是空的
        return head.next == null ;
    }

• 思路
• 首先要根据条件找到要修该的节点,这里用no值查询作为条件
• 仍然是声明第三变量temp作为指针,循环链表,如果no值与链表中的相同就说明找到了要修改的节点.
• 在这里修改有两种思路,第一种是temp指向当前节点,修改当前节点的数据,第二种是temp指向当前节点的上一个节点,也就是说temp.next才是要修改的节点,那么可以将temp.next指向新的节点,新的节点next指向temp.next.next,即原来要修改节点的next,就达到了替换的作用,这里采用第二种方式

public boolean update(Node newNode) { 
        
        //首先需要找到要修改的节点
        Node temp = head;

        //如果为空直接返回
        if(isEmpty()){ 
        
            System.out.println("链表为空");
            return false;
        }
        //遍历链表
        /* 如果当前节点的下一个节点的no值和要修改的节点的no值相同,说明当前节点的下一个节点就是要修改的 节点,此时的temp指针指向的是要修改节点的前一个节点,只需要将前一个节点的next指向新的节点,然后 将新的节点的next指向原来要修改的节点的next,就是将要修改的节点的next值赋给新的节点 */
        while(temp.next != null){ 
        
            //如果找到了相同的no值说明找到了要修改的节点
            if(temp.next.no == newNode.no){ 
        
                /* 首先将要修改节点的next值赋给新节点 , 此时temp.next指向的是要修改的节点,所以要修改节点的 next的值是temp.next.next */
                newNode.next = temp.next.next;
                //然后将当前节点的next指向新的节点
                temp.next = newNode;
                return true;
            }
            //指针后移
            temp = temp.next;
        }
        System.out.println("没有找到该节点");
        return false;
    }

• 思路
• 首先需要明确,单向链表节点的删除是必须靠上一个节点来完成,因为,单向链表是单向的,只能找当前的后面的节点,不能找到前面的节点,而链表的删除则是需要将当前要删除的节点的上一个节点的next的值,指向要删除节点的下一个,由于无法通过当前节点找到上一个节点,所以这里的指针应该指向要删除节点的上一个节点,使用temp.next = temp.next.next的方式.

/** * 删除方法,根据no值来删除 * 该方法与之前修改方法类似,只需将要删除节点的的上一个next直接指向要删除节点的next * @return */
    public boolean del(int no){ 
        
        //第三变量默认指向头结点
        Node temp = head;
        if(isEmpty()){ 
        
            System.out.println("链表为空");
            return false;
        }
        while(temp.next != null){ 
        
            //如果找到了要删除的节点
            if(temp.next.no == no){ 
        
                //就将当前节点的next指向要删除的的next
                //注意此时的temp指向的是要删除节点的前一个
                temp.next = temp.next.next;
                return true ;
            }
            //指针后移
            temp = temp.next;
        }
        System.out.println("没找到要删除的节点");
        return false;
    }

• 思路
• 循环,利用temp指针,每循环一次temp后移一位,当temp.next为null说明链表结束.

  /** * 遍历方法 */
    public void showList(){ 
        
        Node temp = head;
        if (isEmpty()){ 
        
            System.out.println("链表为空");
        }
        while(temp.next != null){ 
        
            System.out.println(temp.next);
            temp = temp.next;
        }
    }

• 思路
• 定义一个计数器,每循环一次,计数器++,仍然是当temp.next为空说明循环结束

   /** * 统计头结点的个数,不包含头结点 */
    public int size(){ 
        
        int size = 0 ;
        Node temp = head.next;
        while(temp != null){ 
        
            size++;
            temp = temp.next;
        }
        return size;
    }

综合代码

public class LinkedList { 
        
    //声明一个头结点.这个节点不放具体的数据,只记录第一个节点的地址
    private Node head = new Node(0 , "" , "");

    /** * 添加方法，这里的添加需要保证插入的Node是新的next是null,如果next的值不为空之前使用过指向另一个 * Node地址的话会出现添加一个却把之前链表都连起来的情况,如果恰巧形成了闭环,首尾相连会出现死循环的情况 * @param newNode * @return */
    public boolean add(Node newNode){ 
        
        //声明一个第三变量用作指针,开始默认指向头结点
        Node temp = head;
        //循环遍历链表,将新节点加入到next为null的节点后,就是直接加入到最后一个节点的后面
        while(true){ 
        
            //如果当前节点的下一个节点是null ,说明该节点是最后一个节点
            if(temp.next == null){ 
        
                //直接将新节点添加到最后一个节点之后,next指向新节点
                temp.next = newNode;
                return true;
            }
            //将指针后移一位,指针指向下一个节点
            temp = temp.next ;
        }
    }

    /** * 判断链表是否为空的方法 * @return */
    public boolean isEmpty(){ 
        
        //如果头结点的下一个是空,就说明链表是空的
        return head.next == null ;
    }

    /** * 修改链表中数据的方法 * 需要提供一个新的节点,根据新节点的id值找到原来的节点,将原数据进行修改,id值不变 * @return */
    public boolean update(Node newNode) { 
        
        //首先需要找到要修改的节点
        Node temp = head;
        //如果为空直接返回
        if(isEmpty()){ 
        
            System.out.println("链表为空");
            return false;
        }
        //遍历链表
        /* 如果当前节点的下一个节点的no值和要修改的节点的no值相同,说明当前节点的下一个节点就是要修改的 节点,此时的temp指针指向的是要修改节点的前一个节点,只需要将前一个节点的next指向新的节点,然后 将新的节点的next指向原来要修改的节点的next,就是将要修改的节点的next值赋给新的节点 */
        while(temp.next != null){ 
        
            //如果找到了相同的no值说明找到了要修改的节点
            if(temp.next.no == newNode.no){ 
        
                /* 首先将要修改节点的next值赋给新节点 , 此时temp.next指向的是要修改的节点,所以要修改节点的 next的值是temp.next.next */
                newNode.next = temp.next.next;
                //然后将当前节点的next指向新的节点
                temp.next = newNode;
                return true;
            }
            //指针后移
            temp = temp.next;
        }
        System.out.println("没有找到该节点");
        return false;
    }

    /** * 遍历方法 */
    public void showList(){ 
        
        Node temp = head;
        if (isEmpty()){ 
        
            System.out.println("链表为空");
        }
        while(temp.next != null){ 
        
            System.out.println(temp.next);
            temp = temp.next;
        }
    }

    /** * 删除方法,根据no值来删除 * 该方法与之前修改方法类似,只需将要删除节点的的上一个next直接指向要删除节点的next * @return */
    public boolean del(int no){ 
        
        //第三变量默认指向头结点
        Node temp = head;
        if(isEmpty()){ 
        
            System.out.println("链表为空");
            return false;
        }
        while(temp.next != null){ 
        
            //如果找到了要删除的节点
            if(temp.next.no == no){ 
        
                //就将当前节点的next指向要删除的的next
                //注意此时的temp指向的是要删除节点的前一个
                temp.next = temp.next.next;
                return true ;
            }
            //指针后移
            temp = temp.next;
        }
        System.out.println("没找到要删除的节点");
        return false;
    }
    
    /** * 统计头结点的个数,不包含头结点 */
    public int size(){ 
        
        int size = 0 ;
        Node temp = head.next;
        while(temp != null){ 
        
            size++;
            temp = temp.next;
        }
        return size;
    }
 }

/*** * 节点 */
class Node{ 
        
    //************数据层************
    public int no;
    public String name ;
    public String nick;
    //******************************
    public Node next;

    public Node(int no , String name , String nick){ 
        
        this.no = no ;
        this.name = name ;
        this.nick = nick ;
    }
    @Override
    public String toString() { 
        
        return "Node{" +
                "no=" + no +
                ", name='" + name + '\'' +
                ", nick='" + nick + '\'' +
                '}';
    }
}

public class Test { 
        
    public static void main(String[] args) { 
        
		LinkedList linkedList = new LinkedList();
        Node n1 = new Node(1 , "宋江" , "及时雨");
        Node n2 = new Node(2 , "卢俊义" , "玉麒麟");
        Node n3 = new Node(3 , "吴用" , "智多星");
        Node n4 = new Node(4 , "李逵" , "黑旋风");
        Node n5 = new Node(5 , "林冲" , "豹子头");

        linkedList.addByOrder(n1);
        linkedList.addByOrder(n3);
        linkedList.addByOrder(n2);
        linkedList.addByOrder(n5);
        linkedList.addByOrder(n4);
        System.out.println("修改之后~~~~~~~");
        Node n6 = new Node(5 , "冲冲" , "豹子头~~~");
        linkedList.update(n6);
        linkedList.showList();
        
        System.out.println("移除之后~~~~~~~");
        linkedList.del(5);
        linkedList.del(1);
        linkedList.del(2);
        linkedList.del(3);
        linkedList.del(4);
        linkedList.showList();
        
        //之前的节点不能使用,需要新建节点,保证next值为null
        Node n11 = new Node(1 , "宋江" , "及时雨");
        Node n7 = new Node(2 , "卢俊义" , "玉麒麟");
        Node n8 = new Node(3 , "吴用" , "智多星");
        Node n9 = new Node(4 , "李逵" , "黑旋风");
        Node n10 = new Node(5 , "林冲" , "豹子头");

        System.out.println("添加之后~~~~~~~");
        linkedList.add(n11);
        linkedList.add(n7);
        linkedList.add(n8);
        linkedList.add(n9);
        linkedList.add(n10);
        linkedList.showList();

双端链表的节点类保留下一节点的引用。（单向引用）

双端链表： 保留对头节点、尾节点的引用，可以从尾节点插入，但只能从头节点删除，只能从一个方向遍历，相当于单向链表多了一个对尾节点的引用。

双端链表的特点： 双端链表的含有对 第一个节点 和 最后一个节点的引用 。

|

双端链表： 只能从一个方向遍历，相当于 单向链表 多了一个对尾节点的引用。