Geordnete verknüpfte Liste:
Nach Schlüsselwert sortieren. Beim Löschen des Linkkopfes wird der minimale (/maximale) Wert gelöscht. Beim Einfügen wird die Einfügeposition gesucht.
Beim Einfügen muss O(N) verglichen werden, der Durchschnitt beträgt O(N/2), beim Löschen der kleinsten (/größten) Daten am Kopf der Kette beträgt die Effizienz O(1),
Wenn eine Anwendung häufiges Speichern erfordert, um das kleinste (/größte) Datenelement abzurufen (einzufügen/suchen/löschen), dann ist die geordnete verknüpfte Liste eine gute Wahl
Die Prioritätswarteschlange kann die geordnete verknüpfte Liste zur Implementierung verwenden
Einfügungssortierung der geordneten verknüpften Liste:
Für ein ungeordnetes Array, bei dem eine geordnete verknüpfte Liste zum Sortieren verwendet wird, beträgt die Vergleichszeitstufe immer noch O(N^2)
Die Kopierzeitstufe beträgt O(2*N ), da die Anzahl der Kopien gering ist, fügen Sie die Daten beim ersten Mal in die verknüpfte Liste ein und verschieben Sie sie N-mal. Kopieren Sie sie dann erneut N-mal aus der verknüpften Liste in das Array.
Jedes Mal, wenn Sie einen neuen Link einfügen Sie müssen die Daten nicht kopieren und verschieben, sondern nur die Linkdomäne von einem oder zwei Linkpunkten ändern
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();
}
}Nach dem Login kopieren
Drucken
----排序前----
[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
Nach dem Login kopieren
Einfach verknüpfte Liste in umgekehrter Reihenfolge:
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;
}
}Nach dem Login kopieren
Weitere Beispiele für die Java-Simulation von geordneten Verknüpfte Listendatenstrukturen und verwandte Artikel beachten Sie bitte die chinesische PHP-Website!
