首页 > 代码库 > JavaBasic 之 LinkedList

JavaBasic 之 LinkedList

一、链表

  1. 基本介绍:

  链表是线性表的一种。线性表是最基本、最简单、也是最常用的一种数据结构。线性表中数据元素之间的关系是一对一的关系,即除了第一个和最后一个数据元素之外,其它数据元素都是首尾相接的。线性表有两种存储方式,一种是顺序存储结构,另一种是链式存储结构。我们常用的数组就是一种典型的顺序存储结构。

  相反,链式存储结构就是两个相邻的元素在内存中可能不是相邻的,每一个元素都有一个指针域,指针域一般是存储着到下一个元素的指针。这种存储方式的优点是定点插入和定点删除的时间复杂度为 O(1),不会浪费太多内存,添加元素的时候才会申请内存,删除元素会释放内存。缺点是访问的时间复杂度最坏为 O(n)。

  顺序表的特性是随机读取,也就是访问一个元素的时间复杂度是O(1),链式表的特性是插入和删除的时间复杂度为O(1)。链表就是链式存储的线性表。根据指针域的不同,链表分为单向链表、双向链表、循环链表等等。

技术分享
1 public class ListNode {
2     public int val ;
3     public ListNode next ;
4     public ListNode(int val){
5         this.val = val ;
6         this.next = null ;
7     }
8 }
View Code

  2. 链表反转

  链表的基本形式是:1 -> 2 -> 3 -> null,反转需要变为 3 -> 2 -> 1 -> null。这里要注意:

  • 访问某个节点 curt.next 时,要检验 curt 是否为 null。
  • 要把反转后的最后一个节点(即反转前的第一个节点)指向 null。
  • 技术分享
     1 package LinkedList;
     2 
     3 class ListNode {
     4     public int val ;
     5     public ListNode next ;
     6     public ListNode(int val){
     7         this.val = val ;
     8         this.next = null ;
     9     }
    10     
    11 
    12     public ListNode reverse(ListNode head){
    13         ListNode prev = null ;
    14         while (head != null) {
    15             ListNode next = prev ;
    16             head.next = prev ;
    17             prev = head ;
    18             head = next ;
    19         }
    20         return prev ;
    21     }
    22 /*
    23  *     public ListNode reverse(ListNode head){
    24         if (head == null || head.next == null) {
    25             return head ;
    26         }
    27         ListNode next = head.next ;
    28         ListNode newHead = reverse(next) ;
    29         next.next = head ;
    30         head.next = null ;
    31         return newHead ;
    32     }
    33  */
    34 
    35 }
    View Code

  3. 双向链表  

技术分享
 1 package LinkedList;
 2 
 3 public class DListNode 
 4 {
 5     int val ;
 6     DListNode prev, next ;
 7     DListNode(int val){
 8         this.val = val ;
 9         this.prev = this.next = null ;
10     }
11     
12     public DListNode reverse(DListNode head){
13         DListNode curr = null ;
14         while(head != null){
15             curr = head ;
16             head = curr.next ;
17             curr.next = curr.prev ;
18             curr.prev = head ;
19         }
20         return curr ;
21     }
22 }
View Code

  4. 链表的鲁棒性    

  链表操作时的鲁棒性问题主要包含两个情况:

  • 当访问链表中某个节点 curt.next 时,一定要先判断 curt 是否为 null。
  • 全部操作结束后,判断是否有环;若有环,则置其中一端为 null。.

参考GitHub。https://algorithm.yuanbin.me/zh-hans/basics_data_structure/linked_list.html#反转链表

JavaBasic 之 LinkedList