源码链接:文章内源码
链表是一种数据存储结构。在Java原生JDK中对于链表也进行了相应实现。 单向链表是链表的其中一种，其主要原理是:
链表是以节点（Node）的形式存储数据，节点对象中存储了要保存的数据。单向链表中的每一个节点中都持有下一个节点的引用（Node next），通过上一个节点就可以找到下一个节点，依次串联，所以想要遍历整个单向链表就需要找到第一个节点。链表不同于数组，在内存中不一定是连续的空间，由于是节点存储，可以利用内存中零散的空间进行保存，只需持有下一个节点的地址即可。很多人都知道链表相较于List他增删快,查询慢,主要因为,链表的修改只需要将前一个节点和后一个节点中所持的前后节点的引用进行修改,而list在进行删除或者增加操作时,往往需要将集合中的元素进行移动,所以较为耗费时间较长,但是,实际上还是需要根据实际情况来判断,如果不考虑随机插入的情况,一直是在最后进行插入,list是非常快的,因为不需要进行元素的移动,但如果是随机插入或者是在靠前的位置进行插入,链表则有很大的优势,所以到底谁快谁慢还是要结合具体问题.在JDK中已经封装好了链表的集合容器,我们直接用就行了,但是手动的实现一些基本功能还是有助于更好的了解底层的原理加深对于这种数据结构的认识。
首先我们需要声明一个头结点Head,这个head不存放具体的数据,只是记录第一个节点的地址。
public class LinkedList { //声明一个头结点.这个节点不放具体的数据,只记录第一个节点的地址 //根据上面的Node的构造方法初始化,next指针先不赋值. private Node head = new Node(0 , "" , ""); }综合代码
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 + '\'' + '}'; } }