有序鏈表：

按關鍵值排序。

刪除鏈頭時，就刪除最小(/最大)的值，插入時，搜索插入的位置。

插入時須要比較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> {

private Link 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 newLink = new Link(data);

Link 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 deleteFirst() {//刪除 鏈頭

Link temp = first;

first = first.next; //變更首結點，為下一結點

return temp;

}

public Link find(T t) {

Link find = first;

while (find != null) {

if (!find.data.equals(t)) {

find = find.next;

} else {

break;

}

}

return find;

}

public Link delete(T t) {

if (isEmpty()) {

return null;

} else {

if (first.data.equals(t)) {

Link temp = first;

first = first.next; //變更首結點，為下一結點

return temp;

}

}

Link p = first;

Link 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 current = first;

while (current != null) {

current.displayLink();

current = current.next;

}

}

public void displayListReverse() {//反序遍歷

Link 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 data;//數據域

Link next; //后繼指針，結點鏈域

Link(T data) {

this.data = data;

}

void displayLink() {

System.out.println("the data is " + data.toString());

}

}

public static void main(String[] args) {

LinkedListInsertSort list = new LinkedListInsertSort();

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

總結

以上是生活随笔為你收集整理的有序链表插入 java_Java 实现有序链表的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。