固定长度有序链表设计

在工作中，经常调用下游服务获取数据，如果数据未按照要求排序，那么需要我们自己来处理，过滤需要的数据。写了个简单的链表结点类，总结一下。

代码

完全脱离公司业务的，代码不多，贴出来，

class SequenceNode<T> {
    int sequence;
    double key;
    T value;
    int maxLength;
    SequenceNode<T> next;

    SequenceNode(T value,int max,int sequence,double key){
        this.value = value;
        this.maxLength = max;
        this.sequence = sequence;
        this.key = key;
    }

    SequenceNode<T> insertAndOrder(T poi,double key) {
        //1. new node is less than head
        if(this.key >= key){
            //if full , then will remove last one 
            if(isFull()){
                removeLast();
            }
            SequenceNode<T> newHead = new SequenceNode<T>(poi,maxLength,1,key);
            newHead.next = this;
            autoIncreaseSequence(newHead);
            return newHead;
        }else{
            SequenceNode<T> insertPoint = findInsertPoint(key);
            if(insertPoint != null){
                if(isFull()){
                    removeLast();
                }
                SequenceNode<T> newNode = new SequenceNode<T>(poi,maxLength,insertPoint.sequence+1,key);
                newNode.next = insertPoint.next;
                insertPoint.next = newNode;
                autoIncreaseSequence(newNode);
            }
        }

        return this;
    }

    private SequenceNode<T> findInsertPoint(double key) {
        //this is head, just skip. begin to compare from next node
        SequenceNode<T> current = this;
        SequenceNode<T> before = null;
        while(current.next != null){
            before = current;
            current = current.next;
            if(current.key >= key){
                return before;
            }
        }

        if(!isFull()){
            return current;
        }
        return null;
    }

    private void autoIncreaseSequence(SequenceNode<T> point) {
        SequenceNode<T> current = point.next ;
        while(current != null){
            current.sequence =  current.sequence+1;
            current = current.next;
        }
    }

    private boolean isFull() {
        return getLastSequence() == maxLength;
    }

    private void removeLast() {
        SequenceNode<T> current = this;
        SequenceNode<T> secondLast = null;
        while(current.next != null){
            secondLast = current;
            current = current.next;
        }
        current = null;
        secondLast.next = null;
    }

    private int getLastSequence() {

        SequenceNode<T> last = this;
        while(last.next != null){
            last = last.next;
        }
        return last.sequence;
    }

    public int getSequence(){
        return this.sequence;
    }

    public T getVaue(){
        return value;
    }

    public List<T> convertToList(){
        List<T> list = new ArrayList<T>();
        SequenceNode<T> current = this;
        list.add(current.getVaue());
        while(current.next != null){
            current = current.next;
            list.add(current.getVaue());
        }
        return list;
    }
}

sequence

序列号，表示第几个元素

key

key是排序的关键，这里直接定义为double类型，通用型可以定义为Object类型。

value

真正需要存储的对象

maxLength

链表最长限制

next

下一个结点引用，可以看出设计的很简单，是单向链表。

对外接口分析

链表只提供4个对外接口，较简单，有更多需要可以扩展。

getSequence

获取序列号，不多说。

getValue

获取存储对象

insertAndOrder

这个方法是核心，保证链表顺序。对外服务时，我只需要维护一个Head结点，然后Head结点一直调用这个方法，插入元素。这应该是直接插入排序，需要维护一个有序的链表，就是Head。

• 插入链表头前面，如果满了，删除最后一个结点，新建结点，next指向头结点，头结点后续所有结点序列都自增1。

  if(isFull()){
      removeLast();
  }
  SequenceNode<T> newHead = new SequenceNode<T>(poi,maxLength,1,key);
  newHead.next = this;
  autoIncreaseSequence(newHead);
  return newHead;

删除最后一个结点方法，这里没有维护尾结点，需要遍历至最后一个结点。如果链表过长，要考虑优化。

private void removeLast() {
    SequenceNode<T> current = this;
    SequenceNode<T> secondLast = null;
    while(current.next != null){
        secondLast = current;
        current = current.next;
    }
    current = null;
    secondLast.next = null;
}

自增序列方法，参数结点不增。

private void autoIncreaseSequence(SequenceNode<T> point) {
    SequenceNode<T> current = point.next ;
    while(current != null){
        current.sequence =  current.sequence+1;
        current = current.next;
    }
}

• 插入链表头后面，找到插入结点位置，判断是否需要删除元素。新增结点并插入。

  SequenceNode<T> insertPoint = findInsertPoint(key);
  if(insertPoint != null){
      if(isFull()){
          removeLast();
      }
      SequenceNode<T> newNode = new SequenceNode<T>(poi,maxLength,insertPoint.sequence+1,key);
      newNode.next = insertPoint.next;
      insertPoint.next = newNode;
      autoIncreaseSequence(newNode);
  }

查找插入点方法，

private SequenceNode<T> findInsertPoint(double key) {
	//this is head, just skip. begin to compare from next node
    SequenceNode<T> current = this;
    SequenceNode<T> before = null;
    while(current.next != null){
        before = current;
        current = current.next;
        if(current.key >= key){
            return before;
        }
    }

    if(!isFull()){
        return current;
    }
    return null;
}

convertToList

将链表转换成List输出。

如何扩展

这简单的链表，看得出遍历的情况很多，如果链表过大时，需要考虑如果优化遍历的性能。在插入结点的时候，是不是可以不需要从链头开始遍历呢？Key可以更加泛化。