Java模拟有序链表数据结构的示例

企鹅博客
企鹅博客
企鹅博客
25193
文章
0
评论
2020年8月29日15:00:20 评论 38 views

有序链表:

按关键值排序。删除链头时,就删除最小(/最大)的值,插入时,搜索插入的位置。

插入时需要比较O(N),平均O(N/2),删除最小(/最大)的在链头的数据时效率为O(1),

如果一个应用需要频繁的存取(插入/查找/删除)最小(/最大)的数据项,那么有序链表是一个不错的选择

优先级队列 可以使用有序链表来实现

有序链表的插入排序:

对一个无序数组,用有序链表来排序,比较的时间级还是O(N^2)

复制时间级为O(2*N),因为复制的次数较少,第一次放进链表数据移动N次,再从链表复制到数组,又是N次

每插入一个新的链结点,不需要复制移动数据,只需要改变一两个链结点的链域

import java.util.Arrays; 
import java.util.Random; 
  
/** 
 * 有序链表 对数组进行插入排序 
 * @author stone 
 */
public class LinkedListInsertSort<T extends Comparable<T>> { 
    
  private Link<T> first;    //首结点 
  public LinkedListInsertSort() { 
      
  } 
    
  public boolean isEmpty() { 
    return first == null; 
  } 
    
  public void sortList(T[] ary) { 
    if (ary == null) { 
      return; 
    } 
    //将数组元素插入进链表,以有序链表进行排序 
    for (T data : ary) { 
      insert(data); 
    } 
    // 
      
  } 
    
  public void insert(T data) {// 插入 到 链头, 以从小到大排序 
    Link<T> newLink = new Link<T>(data); 
    Link<T> current = first, previous = null; 
    while (current != null && data.compareTo(current.data) > 0) { 
      previous = current; 
      current = current.next; 
    } 
    if (previous == null) { 
      first = newLink; 
    } else { 
      previous.next = newLink; 
    } 
    newLink.next = current; 
  } 
    
  public Link<T> deleteFirst() {//删除 链头 
    Link<T> temp = first; 
    first = first.next; //变更首结点,为下一结点 
    return temp; 
  } 
    
  public Link<T> find(T t) { 
    Link<T> find = first; 
    while (find != null) { 
      if (!find.data.equals(t)) { 
        find = find.next; 
      } else { 
        break; 
      } 
    } 
    return find; 
  } 
    
  public Link<T> delete(T t) { 
    if (isEmpty()) { 
      return null; 
    } else { 
      if (first.data.equals(t)) { 
        Link<T> temp = first; 
        first = first.next; //变更首结点,为下一结点 
        return temp; 
      } 
    } 
    Link<T> p = first; 
    Link<T> q = first; 
    while (!p.data.equals(t)) { 
      if (p.next == null) {//表示到链尾还没找到 
        return null; 
      } else { 
        q = p; 
        p = p.next; 
      } 
    } 
      
    q.next = p.next; 
    return p; 
  } 
    
  public void displayList() {//遍历 
    System.out.println("List (first-->last):"); 
    Link<T> current = first; 
    while (current != null) { 
      current.displayLink(); 
      current = current.next; 
    } 
  } 
    
  public void displayListReverse() {//反序遍历 
    Link<T> p = first, q = first.next, t; 
    while (q != null) {//指针反向,遍历的数据顺序向后 
      t = q.next; //no3 
      if (p == first) {// 当为原来的头时,头的.next应该置空 
        p.next = null; 
      } 
      q.next = p;// no3 -> no1 pointer reverse 
      p = q; //start is reverse 
      q = t; //no3 start 
    } 
    //上面循环中的if里,把first.next 置空了, 而当q为null不执行循环时,p就为原来的最且一个数据项,反转后把p赋给first 
    first = p;  
    displayList(); 
  } 
    
  class Link<T> {//链结点 
    T data;   //数据域 
    Link<T> next; //后继指针,结点    链域 
    Link(T data) { 
      this.data = data; 
    } 
    void displayLink() { 
      System.out.println("the data is " + data.toString()); 
    } 
  } 
    
  public static void main(String[] args) { 
    LinkedListInsertSort<Integer> list = new LinkedListInsertSort<Integer>(); 
    Random random = new Random(); 
    int len = 5; 
    Integer[] ary = new Integer[len]; 
    for (int i = 0; i < len; i++) { 
      ary[i] = random.nextInt(1000); 
    } 
    System.out.println("----排序前----"); 
    System.out.println(Arrays.toString(ary)); 
    System.out.println("----链表排序后----"); 
    list.sortList(ary); 
    list.displayList(); 
  } 
}

打印

----排序前----
[595, 725, 310, 702, 444]
----链表排序后----
List (first-->last):
the data is 310
the data is 444
the data is 595
the data is 702
the data is 725

单链表反序:

public class SingleLinkedListReverse {
    
  public static void main(String[] args) {
    Node head = new Node(0);
    Node temp = null;
    Node cur = null;
      
    for (int i = 1; i <= 10; i++) {
      temp = new Node(i);
      if (i == 1) {
        head.setNext(temp);
      } else {
        cur.setNext(temp);
      }
      cur = temp;
    }//10.next = null;
      
    Node h = head;
    while (h != null) {
      System.out.print(h.getData() + "\t");
      h = h.getNext();
    }
    System.out.println();
      
    //反转1
//   h = Node.reverse1(head);
//   while (h != null) {
//     System.out.print(h.getData() + "\t");
//     h = h.getNext();
//   }
      
    //反转2
    h = Node.reverse1(head);
    while (h != null) {
      System.out.print(h.getData() + "\t");
      h = h.getNext();
    }
      
      
  }
}
  
/*
 * 单链表的每个节点都含有指向下一个节点属性
 */
class Node {
  Object data;//数据对象 
  Node next; //下一节点
    
  Node(Object d) {
    this.data = d;
  }
  Node(Object d, Node n) {
    this.data = d;
    this.next = n;
  }
  public Object getData() {
    return data;
  }
  public void setData(Object data) {
    this.data = data;
  }
  public Node getNext() {
    return next;
  }
  public void setNext(Node next) {
    this.next = next;
  }
  //方法1 head被重置
  static Node reverse1(Node head) {
  
    Node p = null; //反转后新的 头
    Node q = head;
    //轮换结果:012,123,234,.... 10 null null
    while (head.next != null) {
      p = head.next;   // 第1个 换成第2个 这时p表示原始序列头中的next
      head.next = p.next; // 第2个 换成第3个
      p.next = q;     //已经跑到第1位置的原第2个的下一个 就要变成 原第1个
      q = p;       //新的第1个 要变成 当前第一个
    }
    return p;
      
  }
  //方法2 head没重置
  static Node reverse2(Node head) {
    //将中间节点的指针指向前一个节点之后仍然可以继续向后遍历链表
    Node p1 = head, p2 = head.next, p3; // 前 中 后
    //轮换结果 :012, 123, 234, 345, 456.... 9 10 null
    while (p2 != null) {
      p3 = p2.next; 
      p2.next = p1; //指向后 变 指向前
      p1 = p2;   //2、3向前挪
      p2 = p3;
    }
    head.next = null;//head没变,当输出到0时,再请求0.next 为1
    return p1;
  }
}

更多Java模拟有序链表数据结构的示例相关文章请关注PHP中文网!

继续阅读
企鹅博客
  • 本文由 发表于 2020年8月29日15:00:20
  • 转载请务必保留本文链接:https://www.qieseo.com/328674.html
css的一些小技巧!页面视觉差!_html/css_WEB-ITnose html教程

css的一些小技巧!页面视觉差!_html/css_WEB-ITnose

相当长的一段时间,现在网站与所谓的“视差”效果一直很受欢迎。 万一你没有听说过这种效果,不同的图像,在不同的方向移动或层主要包括。这导致了一个很好的光学效应,使参观者的注意。 在网页设计中,为了实现这...
匿名

发表评论

匿名网友 填写信息

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: