介绍
线性表 : 是由零个或多个数据元素组成的有限序列。
线性表有两种实现方式:
- 顺序结构存储 : 指的是一段地址连续的存储单元依次存储表中的数据元素。
- 链式结构存储 : 指的是各个元素存储的位置不是连续的, 他们之间通过指针域进行关联。
线性表顺序存储
线性表的顺序存储一般使用 数组 实现, 通过分配一块地址连续的内存空间来存储数据元素。
线性表顺序存储.png
为方便和链式存储结构实现相同的操作，现将对表的操作抽取为接口中：
// List.java
public interface List<E> {
/**
* 添加元素
*
* @param element
*/
void add(E element);
/**
* 添加一个线性表
*
* @param list
*/
void addAll(List<E> list);
/**
* 在指定位置上插入元素
*
* @param index
* @param element
*/
void insert(int index, E element);
/**
* 删除指定位置上元素
*
* @param index
*/
E remove(int index);
/**
* 删除元素
*
* @param element
*/
void remove(E element);
/**
* 替换元素
*
* @param target
* @param replace
*/
void replace(E target, E replace);
/**
* 获取指定位置上的元素
*
* @param index
* @return
*/
E get(int index);
/**
* 清空线性表
*/
void clear();
/**
* 判断线性表是否为空
*
* @return
*/
boolean isEmpty();
/**
* 获取线性表长度
*
* @return
*/
int size();
/**
* 返回某个元素第一次出现的位置
*
* @return
*/
int indexOf(E element);
/**
* 返回某个元素最后一次出现的位置
*
* @param element
* @return
*/
int lastIndexOf(E element);
/**
* 转换成数组
*
* @return
*/
Object[] toArray();
}
线性表顺序存储实现 ：
public class ArrayList<E> implements List<E> {
/**
* 默认容器大小
*/
private int defaultCapacity = 10;
/**
* 存储容器
*/
private Object[] elements;
/**
* 元素个数
*/
private int size;
/**
* 默认容量的构造器
*/
public ArrayList() {
elements = new Object[defaultCapacity];
}
/**
* 指定容器大小构造器
*
* @param capacity
*/
public ArrayList(int capacity) {
elements = new Object[capacity];
}
/**
* 使用已有线性表创建新的线性表
*
* @param list
*/
public ArrayList(List<E> list) {
this();
addAll(list);
}
/**
* 确保容器大小是否可用，是否扩容
*
* @param newSize
*/
public void ensureCapacity(int newSize) {
if (newSize > elements.length) {
increaseCapacity(newSize);
}
}
/**
* 扩大容器大小, 1.5 倍扩容
*/
private void increaseCapacity(int newSize) {
int increasedSize = newSize;
increasedSize = increasedSize + increasedSize >> 1;
try {
elements = Arrays.copyOf(elements, increasedSize);
} catch (OutOfMemoryError error) {
// 扩容失败
error.printStackTrace();
}
}
@Override
public void add(E element) {
ensureCapacity(size + 1);
// size 增加 1
elements[size] = element;
size++;
}
@Override
public void addAll(List<E> list) {
if (list == null) {
return;
}
ensureCapacity(list.size() + size);
System.arraycopy(list.toArray(), 0, elements, size, list.size());
size += list.size();
}
@Override
public void insert(int index, E element) {
if (index < 0 || index > size) {
throw new IllegalArgumentException("index ");
}
ensureCapacity(size + 1);
System.arraycopy(elements, index, elements, index + 1, size - index);
elements[index] = element;
size++;
}
@Override
public E remove(int index) {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
E element = (E) elements[index];
System.arraycopy(elements, index + 1, elements, index, size - index - 1);
size--;
return element;
}
@Override
public void remove(E element) {
}
@Override
public void replace(E target, E replace) {
if (target == null) {
for (int i = 0; i < elements.length; i++) {
if (elements[i] == null) {
elements[i] = replace;
}
}
} else {
for (int i = 0; i < elements.length; i++) {
if (elements[i] == target) {
elements[i] = replace;
}
}
}
}
@Override
public E get(int index) {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
return (E) elements[index];
}
@Override
public void clear() {
elements = new Object[defaultCapacity];
size = 0;
}
@Override
public boolean isEmpty() {
return size == 0;
}
@Override
public int size() {
return size;
}
@Override
public int indexOf(E element) {
if (element == null) {
for (int i = 0; i < size; i++) {
if (elements[i] == null) {
return i;
}
}
} else {
for (int i = 0; i < size; i++) {
if (elements[i].equals(element)) {
return i;
}
}
}
return -1;
}
@Override
public int lastIndexOf(E element) {
if (element == null) {
for (int i = size - 1; i >= 0; i++) {
if (elements[i] == null) {
return i;
}
}
} else {
for (int i = size - 1; i >= 0; i++) {
if (elements[i].equals(element)) {
return i;
}
}
}
return -1;
}
private String outOfBoundsMsg(int index) {
return "Index: " + index + ", Size: " + size;
}
public Object[] toArray() {
return Arrays.copyOf(elements, size);
}
}
线性表顺序存储优缺点
优点 :
- 可以随机访问, 查找时间短 O(1) , 存储密度高;
- 逻辑上相邻的元素,物理上也相邻;
- 无需为表中的元素之间的逻辑关系而增加额外的存储空间;
缺点 :
- 插入, 删除操作时需要移动大量元素;
- 当线性表长度变化较大时,难以确定存储空间的容量;
- 当存储元素的个数小于申请的内存空间长度时,造成空间的浪费;
线性表链式存储
前面讲完了线性表中的顺序存储, 现在来一探究竟线性表的链式存储。线性表的链式存储是用一组任意的存储单元存储表中的数据元素，这组存储单元可以是连续的，也可以是不连续的，也就是说这些元素可以存在内存中未被占用的任意位置。
存储单元由两部分组成： 数据域 和 指针域 ，我们把这中存储单元称之为 节点 。
节点结构.png
其中 数据域 存储元素数据，而指针域 存储后一个节点的 地址， 通常把前后与之相邻的两个节点称之为 前驱节点 和 后继节点。
节点前驱后继.png
remove.png
插入.png
节点使用 Java 描述：
/**
* 描述链表中的节点
*
* @param <E>
*/
public class Node<E> {
/**
* 节点数据域中的数据
*/
public E data;
/**
* 节点指针域中指向下一个节点的指针
*/
public Node<E> next;
public Node() {
}
public Node(E data) {
this.data = data;
}
}
线性表链式存储的实现(增加，删除，获取元素)：
public class LinkedList<E> implements List<E> {
/**
* 头节点
*/
private Node<E> head;
/**
* 元素个数
*/
private int size;
public LinkedList() {
head = new Node<>();
}
public LinkedList(List<E> list) {
this();
addAll(list);
}
@Override
public void add(E element) {
Node<E> node = new Node<>(element);
Node<E> iterator = head;
// 从头节点开始依次遍历
while (iterator.next != null) {
iterator = iterator.next;
}
iterator.next = node;
size++;
}
@Override
public void addAll(List<E> list) {
if (list == null || list.size() == 0) {
return;
}
Node<E> iterator = head.next;
while (iterator.next != null) {
iterator = iterator.next;
}
Node<E> addNodeHead = new Node<>();
Node<E> addIterator = addNodeHead;
E[] elements = (E[]) list.toArray();
for (int i = 0; i < elements.length; i++) {
E data = elements[i];
Node<E> node = new Node<>(data);
addIterator.next = node;
addIterator = node;
}
iterator.next = addNodeHead.next;
size += list.size();
addNodeHead = null;
}
@Override
public void insert(int index, E element) {
check(index);
Node<E> preNode = getNode(index - 1);
Node<E> insertNode = new Node<>(element);
insertNode.next = preNode.next;
preNode.next = insertNode;
size++;
}
@Override
public E remove(int index) {
check(index);
Node<E> preNode = getNode(index - 1);
// 要删除的节点
Node<E> removeNode = preNode.next;
preNode.next = removeNode.next;
E data = removeNode.data;
removeNode.data = null;
removeNode.next = null;
removeNode = null;
size--;
return data;
}
@Override
public void remove(E element) {
Node<E> iterator = head.next;
Node<E> preNode = head;
if (element == null) {
while (iterator != null) {
if (iterator.data == null) {
preNode.next = iterator.next;
iterator.next = null;
iterator = preNode.next;
size--;
continue;
}
preNode = preNode.next;
iterator = iterator.next;
}
} else {
while (iterator != null) {
if (iterator.data.equals(element)) {
preNode.next = iterator.next;
iterator.next = null;
iterator = preNode.next;
size--;
continue;
}
preNode = preNode.next;
iterator = iterator.next;
}
}
}
@Override
public void replace(E target, E replace) {
Node<E> iterator = head.next;
if (target == null) {
while (iterator != null) {
if (iterator.data == null) {
iterator.data = replace;
}
iterator = iterator.next;
}
} else {
while (iterator != null) {
if (iterator.data != null && target.equals(iterator.data)) {
iterator.data = replace;
}
iterator = iterator.next;
}
}
}
@Override
public E get(int index) {
Node<E> node = getNode(index);
return node.data;
}
@Override
public void clear() {
for (Node<E> iterator = head; iterator != null; ) {
Node<E> nextNode = iterator.next;
nextNode.data = null;
nextNode.next = null;
iterator = nextNode;
}
size = 0;
}
@Override
public boolean isEmpty() {
return size == 0;
}
@Override
public int size() {
return size;
}
@Override
public int indexOf(E element) {
Node<E> iterator = head.next;
for (int i = 0; i < size; i++) {
Node<E> node = iterator.next;
if (node.data == element) {
return i;
}
}
return -1;
}
@Override
public int lastIndexOf(E element) {
return 0;
}
@Override
public Object[] toArray() {
Object[] objects = new Object[size];
Node<E> iterator = head.next;
int index = 0;
while (iterator != null) {
objects[index] = iterator.data;
index++;
iterator = iterator.next;
}
return objects;
}
/**
* 根据指定位置获取节点, 调用该方法前需要校验 index， 即调用 check()
*
* @param index
* @return
*/
private Node<E> getNode(int index) {
// index = -1, 获取头节点
if (index == -1) {
return head;
}
Node<E> iterator = head.next;
for (int i = 0; i < index; i++) {
iterator = iterator.next;
}
return iterator;
}
private void check(int index) {
if (index < -1 || index >= size) {
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
}
private String outOfBoundsMsg(int index) {
return "Index: " + index + ", Size: " + size;
}
}
线性表链式存储优缺点
优点：
- 插入，删除元素速度快。
- 内存利用率高，不会浪费内存空间。
- 容量大小不固定，扩展灵活。
缺点：
- 不能随机访问元素，遍历速度慢，必须从第一个开始遍历。
