图片来自 unsplash
链表
链表还分为单向链表和双向链表, 但是这篇文章只说单向链表 , 下次再讲双向链表 .
链表和数组的区别 ?
链表和数组在内存中的区别在于 , 数组的每一个元素的地址是连续的 , 而链表的元素地址是可以不连续的 .关于数组 , 后面的文章也会讲到的 .
链表的元素,怎么构成一个整体 ?
上面说了 , 数组因为元素地址连续 , 有了起始地址和数组长度 , 很方便就构成了一个数组结构 .
那链表的元素地址不连续 , 怎么搞 ?
链表内部 , 每一个元素 , 我们称为一个节点 (Node) , 没一个节点内部有两个属性 , 一个属性用来存储当前节点的信息 (item) , 另一个属性则用来存储下一个节点的对象的引用 (next) , 这就相当于存储了下一个节点的地址 . 所以说,链表的最后一个元素的 next 属性为 null .
方法列表
-
add(Item item): 添加元素 . -
get(int index): 获取相应索引位置的元素 . -
isEmpty(): 判断链表是否为空 . -
size(): 返回链表长度 . -
remove(Item item): 删除指定的元素 .
Item 是 java 的泛型类型 .
代码实现
Node 节点对象
private class Node {
public Item item = null;
public Node next = null;
public Node(Item item) {
this.item = item;
}
}
add(Item item)
public void add(Item item) {
Node node = new Node(item);
if (this.length == 0) {
this.head = node;
} else {
Node current = this.head;
while (current.next != null) {
current = current.next;
}
current.next = node;
}
this.length++;
}
首先判断链表长度是否为零 , 为 0 就直接把新节点设为 head , 如果不为零 , 就遍历到最后一个节点 , 并把最后一个节点的next属性指向新节点 .
get(int index)
public Item get(int index) {
Node current = this.head;
int i = 0;
while (i <= index) {
current = current.next;
i++;
}
return current.item;
}
遍历链表 , 如果给定的索引值超出了链表最大索引 , 会直接报错 .
isEmpty()
public boolean isEmpty() {
return this.length == 0;
}
判断链表是否为空 , 直接判断链表长度是否为 0 就可以了 .
size()
public int size(){
return this.length;
}
获取链表长度 , 返回length属性 .
remove(Item item)
public boolean remove(Item item) {
if (this.head.item != item) {
Node current = this.head;
while (current.next != null) {
if (current.next.item == item) {
current.next = current.next.next;
this.length--;
return true;
}
current = current.next;
}
return false;
}
this.head = this.head.next;
this.length--;
return true;
}
遍历链表 , 每一个链表元素的item属性和给定的item值相比较 , 如果相等 , 将current的上一个元素的next属性指向current的下一个元素的引用 .
OK! 链表 , 到这里就结束了!!!
