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

实现的功能如下：1）创建链表2）添加节点（默认添加和指定位置添加）3）访问某一个节点4）删除节点5）获得链表的长度大小6）判断链表是否为空7）自定义链表的打印格式8）清空链表*注意：要弄清楚节点的前赴 和 后继，删除时要注意赋值的顺序！！！定义 链表中 节点的类Nodepublic 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<size; i++) { str = String.valueOf(i + “:"+ node(i).value + “\n”); builder.append(str); } return builder.toString(); } }测试只实现了一些常用功能，自己写的和工具包中的类对比，会从中get到很多。受益多多~