Node可以作为Link的内部类,并私有,对使用者来说更加纯粹
定义结点
//结点
class Node {
Object value;//承载数据
Node next; //指针
//构造器
public Node(Object value, Node next) {
this.value = value;
this.next = next;
}
}
添加
//链表
class Link {
private Node head;
private Node tail;
private int size;
//添加
public void add(Object val) {
Node newNode = new Node(val, null);
if (head == null) {//如果头引用为空,头和尾都指向新引用
head = tail = newNode;
} else {
tail.next = newNode; //指针指向新引用
tail = newNode; //尾引用指向新引用
}
size++;//计数器自增
}
遍历
//遍历逻辑
private void view(Node current) {//current当前结点
if (current == null) {//链表为空弹栈
return;
}
System.out.println(current.value);//非空就打印该结点承载的数据
view(current.next);//递归
}
//遍历只需要传入头引用即可
public void travel() {
view(head);//递归
}
统计
//统计链表长度,返回计数器即可
public int size() {
return size;
}
删除
//删除(包括头和尾)
public boolean remove(Object val) {
//删除头,把头引用直接指向下一个结点即可
if (head.value.equals(val)) {
head = head.next;
--size;
return true;
}
Node prev = head;
while (prev.next != null) {
if (prev.next.value.equals(val)) {
//删除prev.next
if (prev.next == tail) {//如果当前结点下一个就是尾结点
tail = prev;//尾引用指向尾的上一个结点
}
prev.next = prev.next.next;//删除中间,目标结点的前一个结点的引用指向目标结点的下一个结点的引用
--size;//计数器自减
return true;//删除成功返回true
}
prev = prev.next;//指针指向下一个结点
}
return false;//删除失败返回false
}
}
测试
//测试
public class LinkTest {
public static void main(String[] args) {
Link link = new Link();
link.add("123");
link.add("456");
link.add("aa");
link.add("cc");
link.add("99");
link.add("123");
link.add("a");
link.add("456");
link.add("cc");
link.travel();
System.out.println("link.size() = " + link.size());
System.out.println("------------");
while (link.remove("cc")) ;
link.travel();
System.out.println("link.size() = " + link.size());
System.out.println("------------");
link.add("ibacon");
link.travel();
System.out.println("link.size() = " + link.size());
}
}
测试结果
Q.E.D.