介紹
線性表 : 是由零個或多個數據元素組成的有限序列撤逢。
線性表有兩種實現(xiàn)方式:
- 順序結構存儲 : 指的是一段地址連續(xù)的存儲單元依次存儲表中的數據元素侯谁。
- 鏈式結構存儲 : 指的是各個元素存儲的位置不是連續(xù)的, 他們之間通過指針域進行關聯(lián)诱告。
線性表順序存儲
線性表的順序存儲一般使用 數組 實現(xiàn), 通過分配一塊地址連續(xù)的內存空間來存儲數據元素疗绣。
線性表順序存儲.png
為方便和鏈式存儲結構實現(xiàn)相同的操作鳖谈，現(xiàn)將對表的操作抽取為接口中：
// 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();
/**
* 返回某個元素第一次出現(xiàn)的位置
*
* @return
*/
int indexOf(E element);
/**
* 返回某個元素最后一次出現(xiàn)的位置
*
* @param element
* @return
*/
int lastIndexOf(E element);
/**
* 轉換成數組
*
* @return
*/
Object[] toArray();
}
線性表順序存儲實現(xiàn) ：
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];
}
/**
* 使用已有線性表創(chuàng)建新的線性表
*
* @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);
}
}
線性表順序存儲優(yōu)缺點
優(yōu)點 :
- 可以隨機訪問, 查找時間短 O(1) , 存儲密度高;
- 邏輯上相鄰的元素,物理上也相鄰;
- 無需為表中的元素之間的邏輯關系而增加額外的存儲空間;
缺點 :
- 插入, 刪除操作時需要移動大量元素;
- 當線性表長度變化較大時,難以確定存儲空間的容量;
- 當存儲元素的個數小于申請的內存空間長度時,造成空間的浪費;
線性表鏈式存儲
前面講完了線性表中的順序存儲, 現(xiàn)在來一探究竟線性表的鏈式存儲军俊。線性表的鏈式存儲是用一組任意的存儲單元存儲表中的數據元素侥加，這組存儲單元可以是連續(xù)的，也可以是不連續(xù)的粪躬，也就是說這些元素可以存在內存中未被占用的任意位置担败。
存儲單元由兩部分組成： 數據域 和 指針域 ，我們把這中存儲單元稱之為 節(jié)點 镰官。
節(jié)點結構.png
其中 數據域 存儲元素數據提前，而指針域 存儲后一個節(jié)點的 地址， 通常把前后與之相鄰的兩個節(jié)點稱之為 前驅節(jié)點 和 后繼節(jié)點泳唠。
節(jié)點前驅后繼.png
remove.png
插入.png
節(jié)點使用 Java 描述：
/**
* 描述鏈表中的節(jié)點
*
* @param <E>
*/
public class Node<E> {
/**
* 節(jié)點數據域中的數據
*/
public E data;
/**
* 節(jié)點指針域中指向下一個節(jié)點的指針
*/
public Node<E> next;
public Node() {
}
public Node(E data) {
this.data = data;
}
}
線性表鏈式存儲的實現(xiàn)(增加狈网，刪除，獲取元素)：
public class LinkedList<E> implements List<E> {
/**
* 頭節(jié)點
*/
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;
// 從頭節(jié)點開始依次遍歷
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);
// 要刪除的節(jié)點
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;
}
/**
* 根據指定位置獲取節(jié)點, 調用該方法前需要校驗 index笨腥， 即調用 check()
*
* @param index
* @return
*/
private Node<E> getNode(int index) {
// index = -1, 獲取頭節(jié)點
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;
}
}
線性表鏈式存儲優(yōu)缺點
優(yōu)點：
- 插入孙援，刪除元素速度快。
- 內存利用率高扇雕，不會浪費內存空間拓售。
- 容量大小不固定，擴展靈活镶奉。
缺點：
- 不能隨機訪問元素础淤，遍歷速度慢崭放，必須從第一個開始遍歷。
