有序链表

       链表中有时候需要对数据的顺序有所要求，对于一些应用来说链表中保持数据有序是有意义的一件事，下面就围绕有序链表，说明有序链表的创建和利用链表实现排序。

      在有序链表插入一个数据项，可以采用之前的插入排序的思想，通过局部有序实现数据的排序。插入数据通常在链表中有三种方式：在链表头部、尾部、中间。这三种方式需要考虑到。

有序链表的创建过程

       和一般链表创建一样，首先创建一个结点node，包括一个自身的引用。

class Link3
{
    public int data;
    Link3 next;
    public Link3(int data)
    {
        this.data=data;
    }
    public void showData()
    {
        System.out.println("data "+data);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

       链表添加数据需要考虑几种不同情况，可以将在中间插入数据和链表尾部插入数据归为一类，在表头插入数据是另外一类；

public void add( int key)
    {
        Link3 newNode=new Link3(key);
        //先向链表中添加数据，再进行排序
        Link3 privious=null;
        Link3 current=first;
        while(current!=null&&current.data<key)//指针后移
        {
            privious=current;
            current=current.next;   
        }
        if(privious==null)//如果数据再链表头部插入
        {
            first=newNode;
        }
        //如果不是在链表头部插入
        else
        {
            //newNode=privious;
            privious.next=newNode;
        }
        newNode.next=current;   
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

       添加一个Node主要是两个步骤，将前一个节点的自引用指向该节点，另外该节点的自引用指向下一个节点。引入privious是为了找到上一个节点和要指向的下一个节点。

privious=current;
current=current.next;
1
2

       这是根据数据大小从前向后搜索。除此之外就是常见链表的删除数据和显示操作了。

public Link3 remove()
    {
        Link3 temp=first;
        first=first.next;
        return temp;
    }
public void showList()
    {
        Link3 current=first;
        while(current!=null)
        {
           current.showData();
           current=current.next;
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

测试及测试结果：

        SortLinkList linklist=new SortLinkList();
        linklist.add(1);
        linklist.add(2);
        linklist.add(3);
        linklist.add(4);
        linklist.add(8);
        linklist.add(7);
        linklist.add(6);
        linklist.add(5);
        linklist.showList();
        linklist.remove();
        linklist.remove();
        linklist.showList();
1
2
3
4
5
6
7
8
9
10
11
12
13

data 1
data 2
data 3
data 4
data 5
data 6
data 7
data 8
data 3
data 4
data 5
data 6
data 7
data 8
1
2
3
4
5
6
7
8
9
10
11
12
13
14

有序链表的效率

      有序链表插入和删除某一项最多需要O（N）次比较，但是可以在O（1）时间内删除内找到或删除最小值，因为其总在链表头部。链表可以用于一种高效的排序机制。假设有一个无序数组，如果从这个数组中取出数据，之后将数据插入链表并同时进行插入排序，之后将数据从链表中删除，更新到数组中，这样数组就可以排好序了。这样排序的方式比传统的插入排序要好一些，因为少了一些复制。

下面给出以上示意图的实现代码：

public class SortLinkListArrayApp {

    /**
     * @param args
     */
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int size=8;
        Link4[] linkArray=new Link4[size];
        for(int j=0;j<size;j++)
        {
             int n=(int)(Math.random()*10);
             Link4 newNode=new Link4(n);
             linkArray[j]=newNode;  
        }
        //输出排序之前的数组
        System.out.println("排序之前的数据：");
        for(int k=0;k<size;k++)
        {
            linkArray[k].showData();
        }
        //排序
        SortLinkListArray sortLink=new SortLinkListArray(linkArray);
        //将排序后的数据存入Link数组，更新数据
        for(int m=0;m<size;m++)
        {
            linkArray[m]=sortLink.remove();
        }
        //输出排序后的数组
        System.out.println("排序之后的数据：");
        for(int n=0;n<size;n++)
        {
            //System.out.println(linkArray[n].data);
            linkArray[n].showData();
        }

    }

}
class Link4
{
    public int data;
    Link4 next;
    public Link4(int data)
    {
        this.data=data;
    }
    public void showData()
    {
        System.out.println("data "+data);

    }
}
class SortLinkListArray
{
    Link4 first;
    //此处通过构造函数进行排序 Link数组作为参数进行传递
    public SortLinkListArray(Link4[] linkArr)
    {
        first=null;
        for(int i=0;i<linkArr.length;i++)
        {
            this.add(linkArr[i].data);
        }
    }
    public void add( int key)
    {
        Link4 newNode=new Link4(key);
        //先向链表中添加数据，再进行排序
        Link4 privious=null;
        Link4 current=first;
        while(current!=null&&current.data<key)//指针后移
        {
            privious=current;
            current=current.next;   
        }
        if(privious==null)//如果数据再链表头部插入
        {
            first=newNode;
        }
        //如果不是在链表头部插入
        else
        {
            //newNode=privious;
            privious.next=newNode;
        }
        newNode.next=current;

    }
    public Link4 remove()
    {
        Link4 temp=first;
        first=first.next;
        return temp;
    }
    public void showList()
    {
        Link4 current=first;
        while(current!=null)
        {
           current.showData();
           current=current.next;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105

以下是测试结果：

排序之前的数据：
data 2
data 2
data 4
data 9
data 1
data 3
data 2
data 1
排序之后的数据：
data 1
data 1
data 2
data 2
data 2
data 3
data 4
data 9
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

      每次输入数据不同，因此排序输出也不相同。但是也需要考虑这种排序的劣势：在排序时内存中会同时存在数组和链表。开辟的内存差不多两倍内存大小。但是有现成的有序链表类可用，利用该链表来进行插入排序对不太大的数组排序还是比较便利。