-
简介
线性表是数据结构中最基本的一种结构。能够顺序的存储元素，所存元素在线性表中可以不唯一。线性表有两种实现方式，顺序存储和链式存储。
数据元素之间的关系有两种不同的存储结构:顺序存储结构和链式存储结构。
顺序存储结构是元素在存储器中的相对位置来表示数据元素之间的逻辑关系。
链式存储结构是依靠指针(Java中引用)来表现数据元素之间的逻辑关系。
以下两个数组的两种存储图能够体现出顺序存储结构和链式存储结构的区别。
顺序存储结构和链式存储结构
从上图可看出顺序存储结构:逻辑存储和物理存储相同，链式存储结构:逻辑存储和物理存储不相同
API
public interface List<E> {
/**
* 清空线性表
*/
void clean();
/**
* 判断线性表是否为空
*
* @return true:空，false:非空
*/
boolean isEmpty();
/**
* 获取线性表的元素个数
*
* @return 线性表的元素个数
*/
int length();
/**
* 添加元素
*
* @param elem 添加元素
*/
void addElem(E elem);
/**
* 添加线性表
*
* @param list 待添加的线性表
*/
void addAll(List<? extends E> list);
/**
* 指定位置插入元素
*
* @param index 插入位置
* @param elem 插入元素
*/
void insertElem(int index, E elem);
/**
* 替换元素
*
* @param target 被替换元素
* @param replace 替换元素
* @return 替换的元素个数
*/
int replace(E target, E replace);
/**
* 获取指定位置的元素
*
* @param index 查找位置
* @return 位置对应的元素
*/
E indexOf(int index);
/**
* 查找指定元素的位置
*
* @param elem 待查找元素
* @return 第一次查找到元素的位置
*/
int locateElem(E elem);
/**
* 获取指定元素的所有位置
*
* @param elem 待查找元素
* @return 查找元素的所有位置
*/
List<Integer> locateElements(E elem);
/**
* 批量删除元素
*
* @param elem 待删除的元素
* @return 删除元素的位置
*/
int removeElements(E elem);
/**
* 删除指定位置的元素
*
* @param index 删除的位置
* @return 删除位置的元素
*/
E removeElem(int index);
/**
* 转化为数组
* @return 返回数组
*/
Object[] toArray();
}
-
顺序存储实现(ArrayList)
删除操作:
- 找到删除的位置index
- 将index之后的元素往前面移动一位
伪代码
remove(index, list)
loop i = index up to list.size-2 step 1
index[i] = index[i+1]; //前移
插入操作:
- 将插入位置index的元素和之后的元素往后移动一位
- 将位置index的元素赋值
伪代码
insert(index, list, elem)
loop i = list.size down to index + 1 step 1
list[i] = list[i-1]; //后移
list[index] = elem;
实现
public class ArrayList<E> implements List<E> {
//默认存储容器大小
private int defaultCapacity = 10;
//存储容器
private Object[] elemData;
//元素个数
private int size;
/**
* 初始化存储容器
*/
public ArrayList() {
elemData = new Object[defaultCapacity];
}
/**
* 初始化存储容器并且添加元素
*
* @param initialList 待添加的线性表
*/
public ArrayList(List<? extends E> initialList) {
this();
addAll(initialList);
}
/**
* 初始化存储容器
*
* @param initialCapacity 存储容器初始大小
*/
public ArrayList(int initialCapacity) {
elemData = new Object[initialCapacity];
}
/**
* 检查位置是否合法
*
* @param index 待检查位置
* @throws IndexOutOfBoundsException 位置不合法异常
*/
private void rangeCheck(int index) throws IndexOutOfBoundsException {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException(index + "超出线性表范围");
}
}
/**
* 确保容量够用
*
* @param length 添加后的容量
*/
private void ensureCapacity(int length) {
if (length > elemData.length) {
extendedCapacity(length);
}
}
/**
* 1.5倍扩容
*
* @param length 至少需要的大小
* @throws OutOfMemoryError 分配内存失败
*/
private void extendedCapacity(int length) throws OutOfMemoryError {
int extendedLength = length;
extendedLength = extendedLength + extendedLength >> 1;
try {
elemData = Arrays.copyOf(elemData, extendedLength);
} catch (OutOfMemoryError error) {
throw new OutOfMemoryError("扩容失败");
}
}
public void clean() {
elemData = new Object[defaultCapacity];
size = 0;
}
public boolean isEmpty() {
return size == 0;
}
public int length() {
return size;
}
public void addElem(E elem) {
ensureCapacity(size + 1);
elemData[size++] = elem;
}
public void addAll(List<? extends E> list) {
if (list == null) {
return;
}
ensureCapacity(list.length() + size);
System.arraycopy(list.toArray(), 0, elemData, size, list.length());
size += list.length();
}
public void insertElem(int index, E elem) {
if (index < 0 || index > size) {
throw new IndexOutOfBoundsException(index + "超出线性表范围");
}
ensureCapacity(size + 1);
System.arraycopy(elemData, index, elemData, index + 1, size++ - index);
elemData[index] = elem;
}
public int replace(E target, E replace) {
int count = 0;
if (target == null) {
for (int i = 0; i < size; i++) {
if (elemData[i] == null) {
count++;
elemData[i] = replace;
}
}
} else {
for (int i = 0; i < size; i++) {
if (elemData[i].equals(target)) {
count++;
elemData[i] = replace;
}
}
}
return count;
}
public E indexOf(int index) {
rangeCheck(index);
return (E) elemData[index];
}
public int locateElem(E elem) {
if (elem == null) {
for (int i = 0; i < size; i++) {
if (elemData[i] == null) {
return i;
}
}
} else {
for (int i = 0; i < size; i++) {
if (elemData[i].equals(elem)) {
return i;
}
}
}
return -1;
}
public List<Integer> locateElements(E elem) {
List<Integer> result = new ArrayList<>();
if (elem == null) {
for (int i = 0; i < size; i++) {
if (elemData[i] == null) {
result.addElem(i);
}
}
} else {
for (int i = 0; i < size; i++) {
if (elemData[i] != null && elemData[i].equals(elem)) {
result.addElem(i);
}
}
}
return result;
}
public int removeElements(E elem) {
int result = 0;
List<Integer> list = locateElements(elem);
for (int i = 0; i < list.length(); i++) {
removeElem(list.indexOf(i) - result++);
}
return result;
}
/**
* 删除元素
* 使用System.arrayCopy是调用native方法,效率会比自己写的循环高
* @param index 删除的位置
* @return 删除的元素
*/
public E removeElem(int index) {
E result = (E) elemData[index];
System.arraycopy(elemData, index + 1, elemData, index, size-- - index - 1);
return result;
}
public Object[] toArray() {
return Arrays.copyOf(elemData, size);
}
}
在实现的时候，需要注意size一直比index大于1。在批量删除的时候,索引每次删除都会减去1
-
链式存储实现(LinkedList)
删除操作:
- 找到待删除节点delete的前一个节点prev
- 将prev的next指针指向delete的下一个节点
- 将delete的next指针指向null,帮助GC回收
插入操作: - 找到待插入位置的前一个节点prev
- 新生成一个节点add
- 保存节点after为prev的下一个节点
- 将add节点的next指针指向after
- 将prev节点的next指针指向add
public class LinkedList<E> implements List<E> {
//头结点
private Node<E> head;
//元素个数
private int size;
//节点元素
private class Node<E> {
//节点数据
private E elem;
//指向下一个元素
private Node<E> next;
}
public LinkedList() {
head = new Node<>();
}
public LinkedList(List<? extends E> list) {
this();
addAll(list);
}
/**
* 检查位置是否合法
*
* @param index 待检查位置
* @throws IndexOutOfBoundsException 位置不合法异常
*/
private void rangeCheck(int index) throws IndexOutOfBoundsException {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException(index + "超出线性表范围");
}
}
/**
* 获取指定节点的node
*
* @param index 索引位置
* @return 索引位置的节点
*/
private Node<E> getNode(int index) {
if (index == -1) {
return head;
}
Node<E> iterator = head.next;
for (int i = 0; i < index; i++) {
iterator = iterator.next;
}
return iterator;
}
@Override
public void clean() {
head = null;
size = 0;
}
@Override
public boolean isEmpty() {
return size == 0;
}
@Override
public int length() {
return size;
}
@Override
public void addElem(E elem) {
Node<E> addNode = new Node<>();
addNode.elem = elem;
Node<E> iterator = head;
while (iterator.next != null) {
iterator = iterator.next;
}
iterator.next = addNode;
size++;
}
/**
* 这里没有调用addElem来添加元素
* 原因为:调用addElem添加的时间复杂度为o(n²)
* 使用以下方法添加的时间复杂度为o(n)
* 当然你也可以再添加一个尾节点指针
*
* @param list 待添加的线性表
*/
@Override
public void addAll(List<? extends E> list) {
if (list == null || list.length() == 0) {
return;
}
Node<E> iterator = head;
//时间复杂度O(n)
while (iterator.next != null) {
iterator = iterator.next;
}
Node<E> addNodeHeader = new Node<>();
Node<E> addNodeIterator = addNodeHeader;
//时间复杂度O(n)
E[] addElements = (E[]) list.toArray();
//时间复杂度O(n)
for (int i = 0; i < addElements.length; i++) {
Node<E> node = new Node<>();
node.elem = addElements[i];
addNodeIterator.next = node;
addNodeIterator = node;
}
iterator.next = addNodeHeader.next;
//断开连接,帮助GC回收
addNodeHeader.next = null;
}
@Override
public void insertElem(int index, E elem) {
if (index < 0 || index > size) {
throw new IndexOutOfBoundsException(index + "位置不合法");
}
Node<E> prev = getNode(index - 1);
Node<E> addNode = new Node<>();
addNode.elem = elem;
addNode.next = prev.next;
prev.next = addNode;
size++;
}
@Override
public int replace(E target, E replace) {
Node<E> iterator = head.next;
int result = 0;
if (target == null) {
while (iterator != null) {
if (iterator.elem == null) {
iterator.elem = replace;
result++;
}
iterator = iterator.next;
}
} else {
while (iterator != null) {
if (iterator.elem != null && iterator.elem.equals(target)) {
iterator.elem = replace;
result++;
}
iterator = iterator.next;
}
}
return result;
}
@Override
public E indexOf(int index) {
rangeCheck(index);
//通过上次校验，肯定含有此位置。所以没有按照传统的方法来写。
//传统方法可以参考子标题下面的伪代码
return getNode(index).elem;
}
@Override
public int locateElem(E elem) {
Node<E> iterator = head.next;
int result = 0;
if (elem == null) {
while (iterator != null) {
if (iterator.elem == null)
return result;
result++;
iterator = iterator.next;
}
} else {
while (iterator != null) {
if (iterator.elem != null && iterator.elem.equals(elem)) {
return result;
}
result++;
iterator = iterator.next;
}
}
return -1;
}
@Override
public List<Integer> locateElements(E elem) {
List<Integer> list = new ArrayList<>();
Node<E> iterator = head.next;
int index = 0;
if (elem == null) {
while (iterator != null) {
if (iterator.elem == null) {
list.addElem(index);
}
index++;
iterator = iterator.next;
}
} else {
while (iterator != null) {
if (iterator.elem != null && iterator.elem.equals(elem)) {
list.addElem(index);
}
index++;
iterator = iterator.next;
}
}
return list;
}
@Override
public int removeElements(E elem) {
Node<E> iterator = head.next;
Node<E> prev = head;
int result = 0;
if (elem == null) {
while (iterator != null) {
if (iterator.elem == null) {
prev.next = iterator.next;
iterator.next = null;
iterator = prev.next;
result++;
continue;
}
prev = prev.next;
iterator = iterator.next;
}
} else {
while (iterator != null) {
if (iterator.elem != null && iterator.elem.equals(elem)) {
prev.next = iterator.next;
iterator.next = null;
iterator = prev.next;
result++;
continue;
}
prev = prev.next;
iterator = iterator.next;
}
}
return result;
}
@Override
public E removeElem(int index) {
rangeCheck(index);
Node<E> prev = getNode(index - 1);
Node<E> delNode = prev.next;
prev.next = delNode.next;
E result = delNode.elem;
//help GC
delNode.next = null;
size--;
return result;
}
@Override
public Object[] toArray() {
Node<E> iterator = head.next;
Object[] result = new Object[size];
int loop = 0;
while (iterator != null) {
result[loop++] = iterator.elem;
iterator = iterator.next;
}
return result;
}
}
