手写双向链表LinkedList的几个常用功能

摘要：实现的功能如下创建链表添加节点默认添加和指定位置添加访问某一个节点删除节点获得链表的长度大小判断链表是否为空自定义链表的打印格式清空链表注意要弄清楚节点的前赴和后继，删除时要注意赋值的顺序定义链表中节点的类值前驱后继定义双向链表，实现功能如

实现的功能如下：
1）创建链表
2）添加节点（默认添加和指定位置添加）
3）访问某一个节点
4）删除节点
5）获得链表的长度大小
6）判断链表是否为空
7）自定义链表的打印格式
8）清空链表

*注意：要弄清楚节点的前赴 和 后继，删除时要注意赋值的顺序！！！

定义 链表中 节点的类Node

public class Node {
    
    /**
     * 值
     * 
     */
    Object value;
    
    /**
     * 前驱
     */
    Node pre;
    
    /**
     * 后继
     */
    Node next;
    
    public Node(){
        
    }
    
    public Node(Object value, Node pre, Node next) {
        this.value = value;
        this.pre = pre;
        this.next = next;
    }
}

定义双向链表LinkList，实现功能如下：

/**
 * 双向链表
 * 
 * @author min
 *
 */
public class LinkList {

    /**
     * 头结点
     */
    private Node head;
    
    /**
     * 尾结点
     */
    private Node tail;
    
    private int size;
    
    public LinkList() {
        head = new Node();
        tail = new Node();
        
        head.next = tail;
        tail.pre = head;
        size = 0;
        
    }
    
    public int size() {
        return size;
    }
    
    public boolean isEmpty() {
        return size==0;
    }
    
    public void clear() {
        head.next = tail;
        tail.pre = head;
        size = 0;
    }
    
    /**
     * 在末尾添加新的数据
     * 
     * @param value 数据
     */
    public void add(Object value) {
        Node node = new Node(value,tail.pre,tail);
        tail.pre.next = node;
        tail.pre = node;
        size ++;
        }
    
    /**
     * 在特地位置创建新的节点
     * @param index
     * @param value
     */
    public void add(int index, Object value) {
        checkLinkList(index);
        
        if(index == size -1) {
            //插在最后一位
            add(value);
        }
        else{
            Node x = node(index-1);
            Node y = node(index);
            Node node = new Node(value, x, y);
            x.next = node;
            y.pre = node;
            size ++;
        }        
    }
    
    /**
     * 获取特定位置的节点
     * @param index
     * @return 节点存储的值
     */
    public Object get(int index) {
        //检查是否在链表内
        checkLinkList(index);
        //节点的值
        return node(index).value;
    }

    /**
     * 删除特定的节点
     * @param index
     * @return 被删除的节点
     */
    public Node remove(int index) {
        checkLinkList(index);
        Node x = node(index);
        x.pre.next = x.next;
        x.next.pre = x.pre;
        size --;
        return x;
    }
    

    /**
     * 检查索引是否在链表内
     * 
     * @param index
     */
    private void checkLinkList(int index) {
        if(index > size() ||index < 0)
            throw new ArrayIndexOutOfBoundsException(index);
    }

    /**
     * 遍历链表查询特定的节点
     * 
     * @param index 索引
     * @return 指定的节点
     */
    private Node node(int index) {
        //第1个节点
        Node firstNode = head;
        //最后1个节点
        Node lastNode = tail;
        
        //从头开始遍历
        if(index <=(size>>1) ) {
            Node indexNode = firstNode;
            for(int i = -1; i < index; i++)
                indexNode = indexNode.next;
            return indexNode;
        }
            
        //从尾遍历
        else{            
            Node indexNode = lastNode;
            for(int i = size; i>index; i--) {
                indexNode = indexNode.pre;
            }
            return indexNode;
        }        
    }
    
    /**
     * 重写链表输出方式
     * 
     */
    @Override
    public String toString() {
        StringBuilder builder = new StringBuilder();
        String str = "";
        for(int i = 0; i
测试


只实现了一些常用功能，自己写的和工具包中的类对比，会从中get到很多。受益多多~