一、线性表
线性表可以分为：
- 顺序表（数组）
- 链表（单向链表、双向链表、循环链表）
二、链表
链表是一种链式存储的线性表，所有元素的内存地址不一定是连续的;
三、链表（LinkedList）接口设计
由于链表的大部分接口和动态数组一致，抽取出一个共同的List 接口
public interface List<E> {
static final int ELEMENT_NOT_FOUND = -1;
/**
* 清除所有元素
*/
void clear();
/**
* 元素的数量
* @return
*/
int size();
/**
* 是否为空
* @return
*/
boolean isEmpty();
/**
* 是否包含某个元素
* @param element
* @return
*/
boolean contains(E element);
/**
* 添加元素到尾部
* @param element
*/
void add(E element);
/**
* 获取index位置的元素
* @param index
* @return
*/
E get(int index);
/**
* 设置index位置的元素
* @param index
* @param element
* @return 原来的元素ֵ
*/
E set(int index, E element);
/**
* 在index位置插入一个元素
* @param index
* @param element
*/
void add(int index, E element);
/**
* 删除index位置的元素
* @param index
* @return
*/
E remove(int index);
/**
* 查看元素的索引
* @param element
* @return
*/
int indexOf(E element);
}
单向链表实现（SingleLinkedList）
image.png
` java
public class SingleLinkedList<E> extends AbstractList<E> {
private Node<E> first;
// 链表中的节点
private static class Node<E> {
E element; // 节点元素
Node<E> next; // 节点指向下一个节点
public Node(E element, Node<E> next) {
this.element = element;
this.next = next;
}
}
/**
* 根据索引找到节点对象
*/
private Node<E> node(int index) {
rangeCheck(index);
Node<E> node = first;
for (int i = 0; i < index; i++) {
node = node.next;
}
return node;
}
@Override
public void clear() {
// next 不需要设置为 null，因为 first 指向了 null，后面的 Node 没有被指向，在 Java 中会自动被垃圾回收。
size = 0;
first = null;
}
@Override
public E get(int index) {
return node(index).element;
}
@Override
public E set(int index, E element) {
E old = node(index).element;
node(index).element = element;
return old;
}
@Override
public void add(int index, E element) {
/*
* 最好：O(1)
* 最坏：O(n)
* 平均：O(n)
*/
rangeCheckForAdd(index);
if (index == 0) { // 给空链表添加第一个元素的情况
first = new Node<>(element, first);
} else {
Node<E> prev = node(index - 1);
prev.next = new Node<>(element, prev.next);
}
size++;
}
@Override
public E remove(int index) {
rangeCheck(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;
}
@Override
public int indexOf(E element) {
// 有个注意点, 如果传入元素为null, 则不能调用equals方法, 否则会空指针
// 因此需要对元素是否为null做分别处理
if (element == null) {
Node<E> node = first;
for (int i = 0; i < size; i++) {
if (node.element == null) return i;
node = node.next;
}
} else {
Node<E> node = first;
for (int i = 0; i < size; i++) {
if (node.element.equals(element)) return i;
node = node.next;
}
}
return ELEMENT_NOT_FOUND;
}
@Override
public String toString() {
StringBuilder string = new StringBuilder();
string.append("[size=").append(size).append(", ");
Node<E> node = first;
for (int i = 0; i < size; i++) {
if (i != 0) {
string.append(", ");
}
string.append(node.element);
node = node.next;
}
string.append("]");
return string.toString();
}
}
`
带虚拟头结点的单向链表
为了操作方便，统一所有节点的处理逻辑，可以在最前面增加一个没有实际含义的 虚拟头结点 ，这个虚拟头结点不存储有效数据
image.png
不论是带 虚拟头结点的链表还是不带 虚拟头结点的链表，头指针first都指向链表中的第一个结点。
- 如果该链表有
虚拟头结点，则头指针first指向虚拟头结点 - 如果没有
虚拟头结点，则头指针first指向链表的第一个节点
带虚拟头结点 的单向链表与普通单向链表代码类似：但是 add、reomove 略有不同
` java
/// 增加一个虚拟头结点
public class SingleLinkedList2<E> extends AbstractList<E> {
private Node<E> first;
//**********************************
public SingleLinkedList2() { // 初始化一个虚拟头结点
first = new Node<>(null, null);
};
//**********************************
private static class Node<E> {
E element;
Node<E> next;
public Node(E element, Node<E> next) {
this.element = element;
this.next = next;
}
}
@Override
public void clear() {
size = 0;
first = null;
}
@Override
public E get(int index) {
return node(index).element;
}
@Override
public E set(int index, E element) {
E old = node(index).element;
node(index).element = element;
return old;
}
@Override
public void add(int index, E element) {
rangeCheckForAdd(index);
Node<E> prev = (index == 0) ? first : node(index - 1);
prev.next = new Node<>(element, prev.next);
size++;
}
@Override
public E remove(int index) {
rangeCheck(index);
Node<E> prev = (index == 0) ? first : node(index - 1);
Node<E> node = prev.next;
prev.next = node.next;
size--;
return prev.element;
}
@Override
public int indexOf(E element) {
// 有个注意点, 如果传入元素为null, 则不能调用equals方法, 否则会空指针
// 因此需要对元素是否为null做分别处理
if (element == null) {
Node<E> node = first;
for (int i = 0; i < size; i++) {
if (node.element == null) return i;
node = node.next;
}
} else {
Node<E> node = first;
for (int i = 0; i < size; i++) {
if (node.element.equals(element)) return i;
node = node.next;
}
}
return ELEMENT_NOT_FOUND;
}
/**
* 根据索引找到节点
*
* @param index
* @return
*/
private Node<E> node(int index) {
rangeCheck(index);
Node<E> node = first.next;
for (int i = 0; i < index; i++) {
node = node.next;
}
return node;
}
@Override
public String toString() {
StringBuilder string = new StringBuilder();
string.append("[size=").append(size).append(", ");
Node<E> node = first.next;
for (int i = 0; i < size; i++) {
if (i != 0) {
string.append(", ");
}
string.append(node.element);
node = node.next;
}
string.append("]");
return string.toString();
}
}
`
网友评论