Java simulates an example of an ordered list data structure
- 2020-05-09 18:34:33
- OfStack
Ordered list:
Sort by key value. When the header is removed, the minimum (/ maximum) value is removed, and when inserted, the insertion location is searched.
When inserting, we need to compare O(N), average O(N/2), and O(1) when deleting the smallest (/ largest) data in the header.
If an application requires frequent access (insert/find/delete) of the smallest (/ largest) data items, an ordered list is a good choice
Priority queues can be implemented using ordered lists
Insertion sort of ordered linked list:
If you take an unordered array, and you sort it by an ordered list, the time level of comparison is O(N^2).
Copy time level is O(2*N), because the number of copies is small, the first time put into the linked list data to move N times, and then copy from the linked list to the array, again N times
Each time a new chain node is inserted, there is no need to copy the moving data, only need to change the chain domain of 1 and 2 chain nodes
import java.util.Arrays;
import java.util.Random;
/**
* Order list Insert sort the array
* @author stone
*/
public class LinkedListInsertSort<T extends Comparable<T>> {
private Link<T> first; // The first node
public LinkedListInsertSort() {
}
public boolean isEmpty() {
return first == null;
}
public void sortList(T[] ary) {
if (ary == null) {
return;
}
// Inserts an array element into a linked list , Sort by an ordered list
for (T data : ary) {
insert(data);
}
//
}
public void insert(T data) {// insert to Chain head , From smallest to largest
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 Chain head
Link<T> temp = first;
first = first.next; // Change the first node to below 1 node
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 below 1 node
return temp;
}
}
Link<T> p = first;
Link<T> q = first;
while (!p.data.equals(t)) {
if (p.next == null) {// I haven't found it at the end of the chain
return null;
} else {
q = p;
p = p.next;
}
}
q.next = p.next;
return p;
}
public void displayList() {// traverse
System.out.println("List (first-->last):");
Link<T> current = first;
while (current != null) {
current.displayLink();
current = current.next;
}
}
public void displayListReverse() {// The sequence traversal
Link<T> p = first, q = first.next, t;
while (q != null) {// The pointer is reversed, traversing the data in backward order
t = q.next; //no3
if (p == first) {// When it's the original head, the head .next Should be empty
p.next = null;
}
q.next = p;// no3 -> no1 pointer reverse
p = q; //start is reverse
q = t; //no3 start
}
// In the loop above if In, first.next The empty , And when the q for null When the loop is not executed, p Is the original most and 1 Data items, after the reverse p Assigned to first
first = p;
displayList();
}
class Link<T> {// Chain nodes
T data; // Data fields
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("---- Before ordering ----");
System.out.println(Arrays.toString(ary));
System.out.println("---- The list is sorted ----");
list.sortList(ary);
list.displayList();
}
}
print
---- Before ordering ----
[595, 725, 310, 702, 444]
---- The list is sorted ----
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 in reverse order:
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();
// reverse 1
// h = Node.reverse1(head);
// while (h != null) {
// System.out.print(h.getData() + "\t");
// h = h.getNext();
// }
// reverse 2
h = Node.reverse1(head);
while (h != null) {
System.out.print(h.getData() + "\t");
h = h.getNext();
}
}
}
/*
* Each node in a single linked list contains points down 1 Node properties
*/
class Node {
Object data;// The data object
Node next; // Under the 1 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;
}
// methods 1 head Be reset
static Node reverse1(Node head) {
Node p = null; // Reversed new head
Node q = head;
// Rotation results: 012,123,234,.... 10 null null
while (head.next != null) {
p = head.next; // The first 1 a For the first 2 a At this moment p In the original sequence header next
head.next = p.next; // The first 2 a For the first 3 a
p.next = q; // We're in first place 1 Original order of position 2 A lower 1 a Is about to become The original first 1 a
q = p; // The new first 1 a To become The current first 1 a
}
return p;
}
// methods 2 head No reset
static Node reverse2(Node head) {
// Point the pointer to the middle node forward 1 You can continue to traverse the list after 4 nodes
Node p1 = head, p2 = head.next, p3; // before In the after
// Rotate the results : 012, 123, 234, 345, 456.... 9 10 null
while (p2 != null) {
p3 = p2.next;
p2.next = p1; // After pointing to change Point to the former
p1 = p2; //2 , 3 To move forward
p2 = p3;
}
head.next = null;//head It doesn't change when the output goes to 0 ", then request 0.next for 1
return p1;
}
}