当前位置: 首页 > 编程笔记 >

Java数据结构之链表(动力节点之Java学院整理)

陶炫明
2023-03-14
本文向大家介绍Java数据结构之链表(动力节点之Java学院整理),包括了Java数据结构之链表(动力节点之Java学院整理)的使用技巧和注意事项,需要的朋友参考一下

单链表:

insertFirst:在表头插入一个新的链接点,时间复杂度为O(1)

deleteFirst:删除表头的链接点,时间复杂度为O(1)

find:查找包含指定关键字的链接点,由于需要遍历查找,平均需要查找N/2次,即O(N)

remove:删除包含指定关键字的链接点,由于需要遍历查找,平均需要查找N/2次,即O(N) 

public class LinkedList { 
   private class Data{ 
     private Object obj; 
     private Data next = null;       
     Data(Object obj){ 
       this.obj = obj; 
     } 
   } 
   private Data first = null; 
    
   public void insertFirst(Object obj){ 
     Data data = new Data(obj); 
     data.next = first; 
     first = data; 
   } 
   public Object deleteFirst() throws Exception{ 
     if(first == null) 
       throw new Exception("empty!"); 
     Data temp = first; 
     first = first.next; 
     return temp.obj; 
   }     
   public Object find(Object obj) throws Exception{ 
     if(first == null) 
       throw new Exception("LinkedList is empty!"); 
     Data cur = first; 
     while(cur != null){ 
       if(cur.obj.equals(obj)){ 
         return cur.obj; 
       } 
       cur = cur.next; 
     } 
     return null; 
   } 
   public void remove(Object obj) throws Exception{ 
     if(first == null) 
       throw new Exception("LinkedList is empty!"); 
     if(first.obj.equals(obj)){ 
       first = first.next; 
     }else{ 
       Data pre = first; 
       Data cur = first.next; 
       while(cur != null){ 
         if(cur.obj.equals(obj)){ 
           pre.next = cur.next; 
         } 
        pre = cur; 
         cur = cur.next; 
       } 
     } 
   } 
   public boolean isEmpty(){ 
     return (first == null); 
   } 
   public void display(){ 
     if(first == null) 
       System.out.println("empty"); 
     Data cur = first; 
     while(cur != null){ 
       System.out.print(cur.obj.toString() + " -> "); 
       cur = cur.next; 
     } 
     System.out.print("\n"); 
   }     
   public static void main(String[] args) throws Exception { 
     LinkedList ll = new LinkedList(); 
     ll.insertFirst(4); 
     ll.insertFirst(3); 
     ll.insertFirst(2); 
     ll.insertFirst(1); 
     ll.display(); 
     ll.deleteFirst(); 
     ll.display(); 
     ll.remove(3); 
     ll.display(); 
     System.out.println(ll.find(1)); 
     System.out.println(ll.find(4)); 
   } 
 } 
 1 -> 2 -> 3 -> 4 ->  
 2 -> 3 -> 4 ->  
 2 -> 4 ->  
 null 
 4 

双端链表(不是双向链表):

与单向链表的不同之处在保存有对最后一个链接点的引用(last)

insertFirst:在表头插入一个新的链接点,时间复杂度O(1)

insertLast:在表尾插入一个新的链接点,时间复杂度O(1)

deleteFirst:删除表头的链接点,时间复杂度O(1)

deleteLast::删除表尾的链接点,由于只保存了表尾的链接点,而没有保存表尾的前一个链接点(这里就体现出双向链表的优势了),所以在删除表尾链接点时需要遍历以找到表尾链接点的前一个链接点,需查找N-1次,也就是O(N)
有了这几个方法就可以用双端链表来实现一个队列了

 public class FirstLastList { 
   private class Data{ 
     private Object obj; 
     private Data next = null;       
     Data(Object obj){ 
       this.obj = obj; 
     } 
   }     
   private Data first = null; 
   private Data last = null;     
   public void insertFirst(Object obj){ 
     Data data = new Data(obj); 
     if(first == null) 
       last = data; 
     data.next = first; 
     first = data; 
   }     
   public void insertLast(Object obj){ 
     Data data = new Data(obj); 
     if(first == null){ 
       first = data; 
     }else{ 
       last.next = data;   
     } 
     last = data; 
   }     
   public Object deleteFirst() throws Exception{ 
      if(first == null) 
       throw new Exception("empty"); 
      Data temp = first; 
      if(first.next == null) 
       last = null; 
      first = first.next; 
      return temp.obj; 
  }   
   public void deleteLast() throws Exception{ 
     if(first == null) 
       throw new Exception("empty"); 
     if(first.next == null){ 
       first = null; 
       last = null; 
     }else{ 
       Data temp = first; 
       while(temp.next != null){ 
         if(temp.next == last){ 
           last = temp; 
           last.next = null; 
           break; 
        } 
        temp = temp.next; 
      } 
     } 
   } 
   public void display(){ 
     if(first == null) 
       System.out.println("empty"); 
     Data cur = first; 
     while(cur != null){ 
       System.out.print(cur.obj.toString() + " -> "); 
       cur = cur.next; 
     } 
     System.out.print("\n"); 
   } 
   public static void main(String[] args) throws Exception { 
     FirstLastList fll = new FirstLastList(); 
     fll.insertFirst(2); 
     fll.insertFirst(1); 
     fll.display(); 
     fll.insertLast(3); 
     fll.display(); 
     fll.deleteFirst(); 
     fll.display(); 
     fll.deleteLast(); 
     fll.display(); 
   } 
 } 
 1 -> 2 ->  
 1 -> 2 -> 3 ->  
 2 -> 3 ->  
 2 -> 

有序链表:

链表中的数据按从小到大排列

public class SortedList { 
   private class Data{ 
     private Object obj; 
     private Data next = null;       
     Data(Object obj){ 
       this.obj = obj; 
     } 
   }   
   private Data first = null;     
   public void insert(Object obj){ 
     Data data = new Data(obj); 
     Data pre = null; 
     Data cur = first; 
     while(cur != null && (Integer.valueOf(data.obj.toString()) 
        .intValue() > Integer.valueOf(cur.obj.toString()) 
         .intValue())){ 
       pre = cur; 
      cur = cur.next; 
     } 
     if(pre == null) 
       first = data; 
     else 
       pre.next = data; 
     data.next = cur; 
   }     
   public Object deleteFirst() throws Exception{ 
     if(first == null) 
       throw new Exception("empty!"); 
     Data temp = first; 
     first = first.next; 
     return temp.obj; 
   }     
   public void display(){ 
     if(first == null) 
       System.out.println("empty"); 
     System.out.print("first -> last : "); 
     Data cur = first; 
     while(cur != null){ 
       System.out.print(cur.obj.toString() + " -> "); 
       cur = cur.next; 
     } 
     System.out.print("\n"); 
   }     
   public static void main(String[] args) throws Exception{ 
     SortedList sl = new SortedList(); 
     sl.insert(80); 
     sl.insert(2); 
     sl.insert(100); 
     sl.display(); 
     System.out.println(sl.deleteFirst()); 
     sl.insert(33); 
     sl.display(); 
     sl.insert(99); 
     sl.display(); 
   } 
 } 
 first -> last : 2 -> 80 -> 100 ->  
 2 
 first -> last : 33 -> 80 -> 100 ->  
 first -> last : 33 -> 80 -> 99 -> 100 -> 

表的插入和删除平均需要比较N/2次,即O(N),但是获取最小数据项只需O(1),因为其始终处于表头,对频繁操作最小数据项的应用,可以考虑使用有序链表实现,如:优先级队列和数组相比,链表的优势在于长度不受限制,并且在进行插入和删除操作时,不需要移动数据项,故尽管某些操作的时间复杂度与数组想同,实际效率上还是比数组要高很多。劣势在于随机访问,无法像数组那样直接通过下标找到特定的数据项 。

以上所述是小编给大家介绍的Java数据结构之链表(动力节点之Java学院整理),希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对小牛知识库网站的支持!

 类似资料:
  • 本文向大家介绍Java数据结构与算法之栈(动力节点Java学院整理),包括了Java数据结构与算法之栈(动力节点Java学院整理)的使用技巧和注意事项,需要的朋友参考一下 stack,中文翻译为堆栈,其实指的是栈,heap,堆。这里讲的是数据结构的栈,不是内存分配里面的堆和栈。 栈是先进后出的数据的结构,好比你碟子一个一个堆起来,最后放的那个是堆在最上面的。 队列就是排队买苹果,先去的那个可以先买

  • 本文向大家介绍JavaScript之json_动力节点Java学院整理,包括了JavaScript之json_动力节点Java学院整理的使用技巧和注意事项,需要的朋友参考一下 JSON是JavaScript Object Notation的缩写,它是一种数据交换格式。 在JSON出现之前,大家一直用XML来传递数据。因为XML是一种纯文本格式,所以它适合在网络上交换数据。XML本身不算复杂,但是,

  • 本文向大家介绍JavaScript之iterable_动力节点Java学院整理,包括了JavaScript之iterable_动力节点Java学院整理的使用技巧和注意事项,需要的朋友参考一下 遍历Array可以采用下标循环,遍历Map和Set就无法使用下标。为了统一集合类型,ES6标准引入了新的iterable类型,Array、Map和Set都属于iterable类型。 具有iterable类型的

  • 本文向大家介绍Java线程之join_动力节点Java学院整理,包括了Java线程之join_动力节点Java学院整理的使用技巧和注意事项,需要的朋友参考一下 join()介绍 join() 定义在Thread.java中。 join() 的作用:让“主线程”等待“子线程”结束之后才能继续运行。这句话可能有点晦涩,我们还是通过例子去理解:  说明: 上面的有两个类Father(主线程类)和Son(

  • 本文向大家介绍Spring MVC之DispatcherServlet_动力节点Java学院整理,包括了Spring MVC之DispatcherServlet_动力节点Java学院整理的使用技巧和注意事项,需要的朋友参考一下 Spring MVC之DispatcherServlet 使用Spring MVC,配置DispatcherServlet是第一步。 DispatcherServlet是一

  • 本文向大家介绍Java concurrency之互斥锁_动力节点Java学院整理,包括了Java concurrency之互斥锁_动力节点Java学院整理的使用技巧和注意事项,需要的朋友参考一下 ReentrantLock介绍 ReentrantLock是一个可重入的互斥锁,又被称为“独占锁”。 顾名思义,ReentrantLock锁在同一个时间点只能被一个线程锁持有;而可重入的意思是,Reent