Exemple de Java simulant une structure de données de liste chaînée ordonnée

Liste chaînée ordonnée :
Trier par valeur clé. Lors de la suppression de l'en-tête du lien, la valeur minimale (/maximum) est supprimée. Lors de l'insertion, la position d'insertion est recherchée.
Lors de l'insertion, il faut comparer O(N), moyenne O(N/2), lors de la suppression des plus petites (/plus grandes) données en tête de chaîne, l'efficacité est O(1),
Si une application nécessite un stockage fréquent Pour obtenir (insérer/rechercher/supprimer) l'élément de données le plus petit (/le plus grand), alors la liste chaînée ordonnée est un bon choix
La file d'attente prioritaire peut utiliser la liste chaînée ordonnée pour implémenter
Tri par insertion de la liste chaînée ordonnée :
Pour un tableau non ordonné, en utilisant une liste chaînée ordonnée pour trier, le niveau de temps de comparaison est toujours O(N^2)
Le niveau de temps de copie est O(2*N ), car le nombre de copies est petit, la première fois mettez les données dans la liste chaînée et déplacez-les N fois, puis copiez-les de la liste chaînée vers le tableau, N fois à nouveau
Chaque fois que vous insérez un nouveau lien point, vous n'avez pas besoin de copier et de déplacer les données, il vous suffit de changer le domaine de lien d'un ou deux points de lien

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(); 
  } 
}

Imprimer

----排序前----
[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

Ordre inversé des listes à chaînage unique :

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;
  }
}

Pour plus d'exemples de simulation Java de commandes Structures de données de liste chaînée et articles connexes, veuillez faire attention au site Web PHP chinois !