首页 > 代码库 > Java 实现有序链表
Java 实现有序链表
有序链表:
按关键值排序。
删除链头时,就删除最小(/最大)的值,插入时,搜索插入的位置。
插入时须要比較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 = http://www.mamicode.com/data;>打印----排序前---- [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 实现有序链表
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。