共计 2037 个字符，预计需要花费 6 分钟才能阅读完成。
实现的功能如下：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<size; i++) {
str = String.valueOf(i + “:”+ node(i).value + “\n”);
builder.append(str);
}
return builder.toString();
}
}
测试
只实现了一些常用功能，自己写的和工具包中的类对比，会从中 get 到很多。受益多多~
