【2】单链表
- 1、单链表
- 2、单链表的设计
- 3、接口设计
- 4、SingleLinkedList
- 5、node(int index) 返回索引位置的节点
- 6、clear()
- 7、添加
- 8、删除
- 9、indexOf(E element)
1、单链表
📕动态数组有个明显的缺点
🖊 可能会造成内存空间的大量浪费
📕 能否用到多少就申请多少内存？
🖊 链表可以办到这一点
📕 链表是一种链式存储的线性表，所有元素的内存地址不一定是连续的
🖊 每个节点中有一个成员变量指记录着下一个节点的内存地址
2、单链表的设计
🍀
size存储单链表的节点个数
🍀first被称作头指针：指向头节点
🍀 每个节点（Node）中有element属性存储具体的数据；next属性存储下一个节点的内存地址
🍀 尾节点的next属性为 null
🍀 单链表也是线性表（有索引的概念）
3、接口设计
📕 链表的大部分接口和动态数组是一致的
public interface List<E> {
/**
* 返回存储的元素数量
*/
int size();
/**
* 是否为空
*/
boolean isEmpty();
/**
* 是否包含给定元素
*/
boolean contains(E element);
/**
* 返回索引位置的元素
*/
E get(int index);
/**
* 返回指定元素的索引
*/
int indexOf(E element);
/**
* 添加元素到尾部
*/
void add(E element);
/**
* 往索引位置添加元素
*/
void add(int index, E element);
/**
* 删除索引位置的元素
*
* @return 被删除的元素
*/
E remove(int index);
/**
* 清空所有元素
*/
void clear();
/**
* 设置索引位置的元素
*/
E set(int index, E element);
}
4、SingleLinkedList
📕往单链表中添加一个数据就会创建的一个 Node 对象
public class SingleLinkedList<E> implements List<E> {
private int size;
private Node<E> first;
/**
* 返回存储的元素数量
*/
@Override
public int size() {
return 0;
}
/**
* 是否为空
*/
@Override
public boolean isEmpty() {
return false;
}
/**
* 是否包含给定元素
*/
@Override
public boolean contains(E element) {
return false;
}
/**
* 返回索引位置的元素
*/
@Override
public E get(int index) {
return null;
}
/**
* 返回指定元素的索引
*/
@Override
public int indexOf(E element) {
return 0;
}
/**
* 添加元素到尾部
*/
@Override
public void add(E element) {
}
/**
* 往索引位置添加元素
*/
@Override
public void add(int index, E element) {
}
/**
* 删除索引位置的元素
*
* @return 被删除的元素
*/
@Override
public E remove(int index) {
return null;
}
/**
* 清空所有元素
*/
@Override
public void clear() {
}
/**
* 设置索引位置的元素
*/
@Override
public E set(int index, E element) {
return null;
}
private static final class Node<E> {
private E element;
private Node<E> next;
public Node(E element, Node<E> next) {
this.element = element;
this.next = next;
}
}
}
5、node(int index) 返回索引位置的节点
🖊 若需要
index位置的节点，则从first头指针指向的头节点开始 next index 次即可
/**
* 返回index索引处的节点
*/
private Node<E> node(int index) {
checkIndex(index);
Node<E> node = first;
for (int i = 0; i < index; i++) {
node = node.next;
}
return node;
}
📕 get(int index) 方法
/**
* 返回索引位置的元素
*/
@Override
public E get(int index) {
return node(index).element;
}
📕 set(int index, E element) 方法
/**
* 设置索引位置的元素
*/
@Override
public E set(int index, E element) {
Node<E> node = node(index);
E e = node.element;
node.element = element;
return e;
}
6、clear()
🖊
first头指针指向 null，则头节点会被Java的垃圾回收器回收
🖊 头节点的内存被回收会导致它next指向的节点也被回收，最终整个链表就被清空了
/**
* 清空所有元素
*/
@Override
public void clear() {
first = null;
size = 0;
}
7、添加
🖊 如果
index == 0（把元素添加到头节点位置）：直接让first头指针指向新节点，新节点的next指向之前的头节点
🖊 如果index != 0：① 找到index - 1索引处的节点 prev；② 新节点的next指向 prev.next；③ prev.next 指向新节点
* 往索引位置添加元素
*/
@Override
public void add(int index, E element) {
checkIndex4Add(index);
if (index == 0) {
first = new Node<>(element, first);
} else {
Node<E> prev = node(index - 1);
prev.next = new Node<>(element, prev.next);
}
size++;
}
📕 在编写链表代码时，要注意边界测试，比如 index 为
0、size – 1、size时
| 边界 | 介绍 |
|---|---|
0 | 往头节点位置添加元素 |
size-1 | 边界检查通过 |
size | 往链表尾部添加元素 |
/**
* 添加元素到尾部
*/
@Override
public void add(E element) {
add(size, element);
}
8、删除
🖊 如果
index == 0（删除头节点元素）：直接用头指针first指向first.next
🖊 如果index != 0：① 找到前一个节点prev；②prev.next指向prev.next.next
/**
* 删除索引位置的元素
*
* @return 被删除的元素
*/
@Override
public E remove(int index) {
checkIndex(index);
Node<E> node = first;
if (index == 0) {
first = first.next;
} else {
Node<E> prev = node(index - 1);
node = prev.next;
prev.next = node.next;
}
size--;
return node.element;
}
📕 在编写链表代码时，要注意边界测试，比如 index 为
0、size – 1、size时
| 边界 | 介绍 |
|---|---|
0 | 删除头节点 |
size-1 | 边界检查通过 |
size | 抛异常 |
9、indexOf(E element)
📕 从 first 开始挨个遍历比较
🖊 考虑 element == null 的情况
/**
* 返回指定元素的索引
*/
@Override
public int indexOf(E element) {
Node<E> node = first;
if (element == null) {
for (int i = 0; i < size; i++) {
if (node.element == null) return i;
node = node.next;
}
} else {
for (int i = 0; i < size; i++) {
if (element.equals(node.element)) return i;
node = node.next;
}
}
return ELEMENT_NOT_FOUND;
}
🍀😀 单链表完整代码
