关于链表的知识点有哪些

本篇内容介绍了“关于链表的知识点有哪些”的有关知识，在实际案例的操作过程中，不少人都会遇到这样的困境，接下来就让小编带领大家学习一下如何处理这些情况吧！希望大家仔细阅读，能够学有所成！

一 单向链表

1.1  单向链表原理图

单向链表的一个链结点包含数据域和下一个链结点的指针。头结点也包含数据域和指针域，但是一般为了方便查找，头节点不写数据，最后一个结点的指针指向空。

1.2 实现单向链表的存储等操作

创建一个链结点的实体类

public class Node {      // 数据域     public long data;     // 指针域     public Node next;      public Node(long value){         this.data = value;     } }

1.2.1 插入一个节点

在头节点后插入一个结点，第一步需要将新插入的结点指向头结点指向的结点，第二步将头结点指向新插入的结点。插入结点只需要改变一个引用，所以复杂度为O(1)。

public class LinkList {      private Node head;     /**      * 在头节点之后插入一个节点      */     public void insertFirst(long value){         Node node = new Node(value);         node.next = head;         head = node;     } }

1.2.2 头结点后删除一个结点

在头结点后删除一个结点，就是让头结点指向这个结点的下一个结点。复杂度也是O(1)。

public Node deleteFirst(){     Node tmp = head;     head = tmp.next;     return tmp; }

1.2.3 根据数据域查找结点

查找需要比对每个结点的数据，理论上查找一个结点平均需要N/2次，所以复杂度为O(N)。

public Node find(long value){      Node current = head;     while (current.data != value){         if(current.next == null){             return null;         }         current = current.next;     }     return current; }

1.2.4 根据数据与删除结点

查找需要比对每个结点的数据，理论上删除一个结点平均需要N/2次，所以复杂度为O(N)。

public Node delete(int value){     Node current = head;     // 当前结点的前一个结点     Node pre = head;     while (current.data != value){         if(current.next == null){             return null;         }         pre = current;         current = current.next;     }     if(current == head){         head = head.next;     }else{         pre.next = current.next;     }     return current; }

二 双端链表

2.1 双端链表原理图

双端链表是在单向链表的基础上，头结点增加了一个尾结点的引用。

2.2 实现双端链表的存储等操作

2.2.1 从头部插入结点

如果链表为空，则设置尾结点就是新添加的结点。复杂度为O(1)。

public class FirstLastLinkList {      private Node first;     private Node last;     /**      * 在头结点之后插入一个节点      */     public void insertFirst(long value){         Node node = new Node(value);         if(first == null){             last = node;         }         node.next = first;         first = node;     } }

2.2.2 从尾部插入结点

如果链表为空，则设置头结点为新添加的结点，否则设置尾结点的后一个结点为新添加的结点。复杂度为O(1)。

public void insertLast(long value){     Node node = new Node(value);     if(first == null){         first = node;     }else{         last.next = node;     }     last = node; }

2.2.3 从头部进行删除

判断头结点是否有下一个结点，如果没有则设置尾结点为null，复杂度为O(1)。

public Node deleteFirst(){      Node tmp = first;     if(first.next == null){         last = null;     }     first = tmp.next;     return tmp; }

三 双向链表

3.1 双向链表原理图

每个结点除了保存对后一个结点的引用外，还保存着对前一个结点的引用。

3.2 实现双向链表的存储等操作链结点实体类

public class Node {      // 数据域     public long data;     // 后一个结点指针域     public Node next;     // 前一个结点指针域     public Node prev;      public Node(long value){         this.data = value;     } }

3.2.1 从头部插入结点

如果链表为空，则设置尾结点为新添加的结点，如果不为空，还需要设置头结点的前一个结点为新添加的结点。插入结点只需要改变两个结点的引用，所以复杂度为O(1)。

public class DoubleLinkList {      private Node first;     private Node last;      /**      * 在头结点之后插入一个节点      */     public void insertFirst(long value){         Node node = new Node(value);         if(first == null){             last = node;         } else{             first.prev = node;         }         node.next = first;         first = node;     } }

3.2.2 从尾部插入结点

如果链表为空，则设置头结点为新添加的结点，否则设置尾结点的后一个结点为新添加的结点。同时设置新添加的结点的前一个结点为尾结点。插入结点只需要改变1个结点的引用，所以复杂度为O(1)。

public void insertLast(long value){     Node node = new Node(value);     if(first == null){         first = node;     }else{         last.next = node;         node.prev = last;     }     last = node; }

3.2.3 从头部删除结点

判断头结点是否有下一个结点，如果没有则设置尾结点为null，否则设置头结点的下一个结点的prev为null。复杂度也为O(1)。

public Node deleteFirst(){      Node tmp = first;     if(first.next == null){         last = null;     }else{         first.next.prev = null;     }     first = tmp.next;     return tmp; }

3.2.4 从尾部删除结点

如果头结点后没有其他结点，则设置头结点为null，否则设置尾结点的前一个结点的next为null，设置尾结点为前一个结点。复杂度为O(1)。

public Node deleteLast(){      Node tmp = last;      if(first.next == null){         first = null;     }else{         last.prev.next = null;       }     last = last.prev;     return last; }

“关于链表的知识点有哪些”的内容就介绍到这里了，感谢大家的阅读。如果想了解更多行业相关的知识可以关注亿速云网站，小编将为大家输出更多高质量的实用文章！