java数据结构之单链表类的设计与顺序插入和就地排序算法数据结构

首先创建节点类Node. 【java数据结构之单链表类的设计与顺序插入和就地排序算法】单链表是由节点构成，节点类包含两个成员属性，一个是数据元素，一个是下一个节点的对象引用。

class Node { private Object element; //数据元素 private Node next; //下一个节点的对象引用 Node(Node next)//头节点构造函数 { this.element=null; this.next=next; } Node(Object element,Node next)//一般节点构造函数 { this.element=element; this.next=next; } public Object getElement() { return element; } public void setElement(Object element) { this.element = element; } public Node getNext() { return next; } public void setNext(Node next) { this.next = next; } public String toString() { return element.toString(); } }

其次创建单链表类单链表类成员变量包含头节点、当前节点、链表中数据元素个数。

class SingList { Node head; //头节点 Node current; //当前节点 private int size; //链表内数据总数public void setSize(int i)//设置链表长度 { this.size=i; }SingList()//空链表构造函数，当前节点和头节点是同一个节点，且指向的新节点为空，所以用new Node(null) { this.head=this.current=new Node(null); //构造函数里加一句：head.next=head; 在index函数里把循环条件“current!=null”改为“current!=head”即可转化为循环链表 size=0; }public void index(int i) throws Exception//定位到当前节点，即将链表中第i个节点作为当前节点 { if(i<-1||i>size-1)//这里判断条件是i<-1，而不是i<0,是因为后面insert函数里的需要。 { throw new Exception("参数有误!"); } if(i==-1) { current=head; return; }int j=0; current=head.getNext(); //将当前节点设置为头结点指向的第一个节点 while(current!=null&&jsize) { throw new Exception("参数有误!"); } index(i-1); //把当前节点设置为插入点的前一个节点 current.setNext(new Node(obj,current.getNext())); size++; }public Object delete(int i) throws Exception//删除 { if(size==0) { throw new Exception("链表已空!"); } if(i<0||i>size-1) { throw new Exception("参数有误!"); } index(i-1); Object o=current.getNext().getElement(); current.setNext(current.getNext().getNext()); size--; return o; }public Object getDate(int i) throws Exception//获取某个节点的数据 { if(size==0) { throw new Exception("链表已空!"); } if(i<0||i>size-1) { throw new Exception("参数有误!"); } index(i); return current.getElement(); }public int size() { return size; }public boolean isEmpty() { return size==0; }public void add(Object o) throws Exception//向链表中添加数据 { if(size==0) { current.setNext(new Node(o,null)); size++; } else { index(size-1); current.setNext(new Node(o,null)); size++; }} }

顺序插入方法设计思想：从单链表的第一个数据开始，逐个比较每个节点的数据元素与要插入的数据，当节点数据小于插入数据时，进行下一个节点的比较，否则，就找到了插入位置。如果是比较到最后一个节点仍然满足节点数据小于插入数据，则数据插入在链表结尾处。
这里，我先创建了一个的比较器类，实现了Comparator接口，重写了compare方法。

/** * 定义自己的比较器 */ class MyComparator implements Comparator {@Override public int compare(Object o1, Object o2) { // TODO Auto-generated method stub if((o1 instanceof Integer)&&(o2 instanceof Integer)) { Integer i1=(Integer)o1; Integer i2=(Integer)o2; int a=i1.intValue(); int b=i2.intValue(); if(i1>=i2) return 1; else return -1; } else { return 0; } } }

然后新建了InsertSorted类，里面只定义了有序插入的静态方法。

class InsertSorted{ public static void orderInsert(SingList sl,Object o,MyComparator mc){ Node curr; //当前节点 Node pre; //前一个节点curr=sl.head.getNext(); //初始当前节点为第一个节点 pre=sl.head; //初始前节点为头结点while(curr!=null&&mc.compare(curr.getElement(), o)==-1)//循环判断条件：当前节点值不为空且当前节点值小于插入值 { pre=curr; curr=curr.getNext(); //进行下一个节点的判断，直到找出插入位置} Node temp=new Node(o,pre.getNext()); pre.setNext(temp); //完成插入 sl.setSize(sl.size()+1); } }

就地插入方法设计思想：借助有序插入算法，先将原链表数据清空，只保留一个头结点，然后将原链表数据一个个重新有序插入链表，则可以在不创建新节点空间的前提下完成链表的排序。

/** * 就地排序 */ class Sorted{ public static void SortList(SingList sl,MyComparator cm) { Node curr; //定义当前节点 curr=sl.head.getNext(); //将头节点指向的第一个数据节点赋值给当前节点 sl.head.setNext(null); //将原链表清空，仅保留头结点 sl.setSize(0); //链表长度设为0，即无数据节点 while(curr!=null)//当前节点为空时，说明原链表全部数据插入完毕，退出循环 { InsertSorted.orderInsert(sl, curr.getElement(), cm); curr=curr.getNext(); } } }

测试程序贴不下了，大家可以自行尝试~数据结构很枯燥，希望自己坚持下去，慢慢学！