Java模拟有序链表数据结构的示例
程序员文章站
2024-03-11 15:30:31
有序链表:
按关键值排序。删除链头时,就删除最小(/最大)的值,插入时,搜索插入的位置。
插入时需要比较o(n),平均o(n/2),删除最小(/最大)的在链头的数据时效...
有序链表:
按关键值排序。删除链头时,就删除最小(/最大)的值,插入时,搜索插入的位置。
插入时需要比较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; } }