有序链表

￡神魔★判官ぃ 2022-07-18 04:20 180阅读 0赞

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

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

## 有序链表的创建过程 ##

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

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

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

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;   
        }

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

privious=current;
    current=current.next;

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

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;
            }
        }

### 测试及测试结果： ###

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();

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

## 有序链表的效率 ##

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

![这里写图片描述][20160905225944044]

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

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;
            }
        }
    }

### 以下是测试结果： ###

排序之前的数据：
    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

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

[20160905225944044]: /images/20220717/ae138383b4ca4dbe8d8f27ec85027f84.png