순서가 지정된 연결 목록:
키 값으로 정렬합니다. 링크헤드 삭제시 최소(/최대)값이 삭제되며 삽입시 삽입 위치를 검색합니다.
삽입할 때 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; } }
순서 연결 목록 데이터 구조의 Java 시뮬레이션에 대한 추가 예 및 관련 기사는 PHP 중국어 홈페이지를 주목해주세요!