Ordered link list:
Sort by key values. When deleting the chain header, the minimum (/maximum) value is deleted. When inserting, search for the insertion position.
When inserting, you need to compare O(N), average O(N/2), and when deleting the minimum (/maximum) data at the chain head, the efficiency is O(1),
If an application requires frequent access (insert/find/delete) to the smallest (/maximum) data items, then ordered linked lists are a good choice. Priority queues can use ordered linked lists to implement insertion sorting of ordered linked lists:
For an unordered array, sort it with an ordered linked list, and the time level of comparison is O(N^2)
The copy time level is O(2*N). Because the number of copies is small, the data in the linked list is moved N times for the first time, and then copied from the linked list to the array. N times, each time a new link is inserted, there is no need to copy the moving data, only one or two links need to change the link domain.
import java.util.Arrays; import java.util.Random; /** * Insert-sorting arrays in an ordered linked list* @author stone */ public class LinkedListInsertSort<T extends Comparable<T>> { private Link<T> first; //first node public LinkedListInsertSort() { } public boolean isEmpty() { return first == null; } public void sortList(T[] ary) { if (ary == null) { return; } //Insert array elements into the linked list and sort them in an ordered linked list for (T data : ary) { insert(data); } // } public void insert(T data) {// Insert to the chain header, sort from small to large 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() {//Delete the chain header Link<T> temp = first; first = first.next; //Change the first node to 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; //Change the first node to the next node return temp; } } Link<T> p = first; Link<T> q = first; while (!p.data.equals(t)) { if (p.next == null) {//Indicate that return null has not been found at the end of the chain; } else { q = p; p = p.next; } } q.next = p.next; return p; } public void displayList() {//Travel System.out.println("List (first-->last):"); Link<T> current = first; while (current != null) { current.displayLink(); current = current.next; } } public void displayListReverse() {//Inverse traversal Link<T> p = first, q = first.next, t; while (q != null) {//Pointer is reversed, the traversed data order is backward t = q.next; //no3 if (p == first) {// When it is the original header, the .next of the header should be empty p.next = null; } q.next = p;// no3 -> no1 pointer reverse p = q; //start is reverse q = t; //no3 start } //In the if in the loop above, first.next is empty, and when q is null and does not execute the loop, p is the original most data item. After inverting, p is assigned to first first = p; displayList(); } class Link<T> {//link point T data; //Data field Link<T> next; //Subsequent pointer, node chain domain 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(); } }
Print
---Before sorting---- [595, 725, 310, 702, 444] ---After sorting of linked list---- List (first-->last): the data is 310 the data is 444 the data is 595 the data is 702 the data is 725
Single linked list inversion:
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(); // Invert 1 // h = Node.reverse1(head); // while (h != null) { // System.out.print(h.getData() + "/t"); // h = h.getNext(); // } // Invert 2 h = Node.reverse1(head); while (h != null) { System.out.print(h.getData() + "/t"); h = h.getNext(); } } } /* * Each node of a single linked list contains attributes pointing to the next node*/ class Node { Object data;//Data object Node next; //Next node 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; } //Method 1 head is reset static Node reverse1(Node head) { Node p = null; //The new head after inversion Node q = head; //Rotation result: 012,123,234,...... 10 null null while (head.next != null) { p = head.next; //The first one is replaced by the second one, and then p represents next head.next = p.next; //The second one is replaced by the third one, and the next one that has already reached the first position will become the first one, and the first one will become the first one; //The new one is replaced by the first one} return p; } //Method 2 head does not reset static Node reverse2(Node head) { //Point the pointer of the intermediate node to the previous node, you can still continue to traverse the linked list backwards Node p1 = head, p2 = head.next, p3; //Front, middle and back/Rotation result: 012, 123, 234, 345, 456.... 9 10 null while (p2 != null) { p3 = p2.next; p2.next = p1; //Point backwards and point forwards p1 = p2; //2, 3 moves forwards p2 = p3; } head.next = null;//Head has not changed. When the output reaches 0, request 0.next to 1 return p1; } }