java有序链表是一个不错的选择
时间:2021-04-23

有序链表:

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

插入时需要比较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;

  }

}