数据结构-有序链表

1）前面的链表实现插入数据都是无序的，在有些应用中需要链表中的数据有序，这称为有序链表。

在有序链表中，数据是按照关键值有序排列的。一般在大多数需要使用有序数组的场合也可以使用有序链表。有序链表优于有序数组的地方是插入的速度（因为元素不需要移动），另外链表可以扩展到全部有效的使用内存，而数组只能局限于一个固定的大小中。

public class OrderLinkedList {

private Node head;

private int size;//链表节点的个数

private class Node{

private double data;

private Node next;

public Node(double data){

this.data = data;

}

}

//插入节点，并按照从小打到的顺序排列,这里的话可以结合图片来开

public void insert(double value){

Node node = new Node(value);

Node preTmp = null;//前节点

Node current = head;

while(current != null && value > current.data){

preTmp = current;

current = current.next;//current指向的地址 赋值给 current

}

if(preTmp == null){//1

head = node;

head.next = current;

}else{

preTmp.next = node;

node.next = current;

}

size++;

}

//显示节点信息

public void display(){

if(size >0){

Node node = head;

int tempSize = size;

if(tempSize == 1){//当前链表只有一个节点

System.out.println("["+node.data+"]");

return;

}

while(tempSize>0){

if(node.equals(head)){//判断是否是头节点

System.out.print("["+node.data+"->");

}else if(node.next == null){

System.out.print(node.data+"]");

}else{

System.out.print(node.data+"->");

}

node = node.next;

tempSize--;

}

System.out.println();

}else{

//如果链表一个节点都没有，直接打印[]

System.out.println("[]");

}

}

//删除头节点

public void deleteHead(){

head = head.next;

size--;

}

}

class test2{

public static void main(String[] args) {

OrderLinkedList orderLinkedList=new OrderLinkedList();

orderLinkedList.insert(32.25);

orderLinkedList.insert(23.25);

orderLinkedList.insert(41.25);

orderLinkedList.insert(15.25);

System.out.println("链表数据:");

orderLinkedList.display();

System.out.println("删除链头后的数据:");

orderLinkedList.deleteHead();

orderLinkedList.display();

}

}

/**

链表数据:

[15.25->23.25->32.25->41.25]

删除链头后的数据:

[23.25->32.25->41.25]

*/