溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
本篇內容介紹了“什么是線性表、順序表、鏈表”的有關知識，在實際案例的操作過程中，不少人都會遇到這樣的困境，接下來就讓小編帶領大家學習一下如何處理這些情況吧！希望大家仔細閱讀，能夠學有所成！
首先來看一下線性表，順序表，和鏈表之間的區別和聯系：
線性表：
邏輯結構， 就是對外暴露數據之間的關系，不關心底層如何實現，數據結構的邏輯結構大分類就是線性結構和非線性結構，而順序表、鏈表都是一種線性表。
線性表結構存儲的數據往往是可以依次排列的，就像小朋友手拉手，每位學生的前面和后面都僅有一個小朋友和他拉手，具備這種“一對一”關系的數據就可以使用線性表來存儲。
順序表、鏈表：物理結構，他是實現一個結構實際物理地址上的結構。比如順序表就是用數組實現。而鏈表用指針完成主要工作。不同的結構在不同的場景有不同的區別。
我們首先定義一個線性表的抽象類，主要包括增加、查找、刪除等方法。后面分別用順序表和鏈表做實現：
/**
* 線性表
*
* @author ervin
* @Date 2021/4/18
*/
public interface ListInterface<T> {
/**
* 初始化
* @param size
*/
void init(int size);
/**
* 長度
* @return
*/
int length();
/**
* 是否為空
* @return
*/
boolean isEmpty();
/**
* 獲取元素下標
* @param t
* @return
*/
int eleIndex(T t);
/**
* 根據index獲取數據
* @param index
* @return
* @throws Exception
*/
T getEle(int index) throws Exception;
/**
* 根據index插入數據
* @param index
* @param t
* @throws Exception
*/
void add(int index,T t) throws Exception;
/**
* 刪除元素
* @param index
* @throws Exception
*/
void delete(int index) throws Exception;
/**
* 尾部插入元素
* @param t
* @throws Exception
*/
void add(T t) throws Exception;
/**
* 修改
* @param index
* @param t
* @throws Exception
*/
void set(int index,T t) throws Exception;
}順序表是基于數組實現的，由于數組中的數據時存儲的一塊連續的內存中，插入、刪除元素會導致部分元素的移動，效率較低，但是查詢效率卻十分快。
順序表元素插入示意圖：
這里以插入為例做說明，刪除操作正好相反。
如果要刪除下標為 2 的元素時，下標為 2 及之后的元素，從左至右，依次左移一位。
另外，順序表的插入需要考慮 “擴容”
代碼實現：
/**
* 順序表實現
*
* @author ervin
* @Date 2021/4/18
*/
public class SeqList<T> implements ListInterface<T> {
//數組存放數據
private Object[] date;
private int length;
public SeqList() {
//初始大小默認為10
init(10);
}
@Override
public void init(int initSize) {
this.date = new Object[initSize];
length = 0;
}
@Override
public int length() {
return this.length;
}
@Override
public boolean isEmpty() {
//是否為空
return this.length == 0;
}
@Override
public int eleIndex(T t) {
for (int i = 0; i < date.length; i++) {
if (date[i].equals(t)) {
return i;
}
}
return -1;
}
@Override
public T getEle(int index) throws Exception {
if (index < 0 || index > length - 1) {
throw new Exception("數值越界");
}
return (T) date[index];
}
@Override
public void add(T t) throws Exception {
//尾部插入
add(length, t);
}
@Override
public void add(int index, T t) throws Exception {
if (index < 0 || index > length) {
throw new Exception("數值越界");
}
//擴容
if (length == date.length) {
Object[] newDate = new Object[length * 2];
for (int i = 0; i < length; i++) {
newDate[i] = date[i];
}
date = newDate;
}
//后面元素后移動
for (int i = length - 1; i >= index; i--) {
date[i + 1] = date[i];
}
//插入元素
date[index] = t;
length++;
}
@Override
public void delete(int index) throws Exception {
if (index < 0 || index > length - 1) {
throw new Exception("數值越界");
}
//index之后元素前移動
for (int i = index; i < length; i++) {
date[i] = date[i + 1];
}
length--;
}
@Override
public void set(int index, T t) throws Exception {
if (index < 0 || index > length - 1) {
throw new Exception("數值越界");
}
date[index] = t;
}
}鏈表存儲數據的空間是不連續的，有一個個 “node” 連接起來，形成鏈表，每一個 “node” 不僅存放數據本身，還存放了下一個 “node” 的地址。
如圖：
鏈表查找元素，需要遍歷查找，效率較低；插入刪除元素，只需要，修改指針，效率很高。
鏈表無需考慮 “擴容”
鏈表元素插入示意：
鏈表元素刪除示意圖：
代碼實現：
/**
* 鏈表實現
*
* @author ervin
* @Date 2021/4/18
*/
public class LinkList<T> implements ListInterface<T> {
private static class Node<T> {
T item;
Node<T> next;
Node(T element, Node<T> next) {
this.item = element;
this.next = next;
}
}
Node header;
private int size;
public LinkList(){
this.header = new Node(null,null);
this.size = 0;
}
@Override
public void init(int size) {
}
@Override
public int length() {
return this.size;
}
@Override
public boolean isEmpty() {
return this.length() == 0;
}
@Override
public int eleIndex(T t) {
Node n = header.next;
int index = 0;
while (n.next != null){
if (n.item.equals(t)){
return index;
}
index++;
n = n.next;
}
//找不到返回-1
return -1;
}
@Override
public T getEle(int index) throws Exception {
Node n = getNode(index);
return (T)n.item;
}
@Override
public void add(int index, T t) throws Exception {
//考慮第一個元素
if (index == 0){
this.header.next = new Node(t,null);
} else {
Node n = getNode(index - 1);
//獲取到index的上一個元素n, n指向新建的元素，同時新建的元素指向n的下一個元素
n.next = new Node(t,n.next);
}
this.size++;
}
@Override
public void delete(int index) throws Exception {
//index為0時，不用去獲取上一個元素，
if (index == 0){
this.header.next = getNode(1);
} else {
Node n = getNode(index - 1);
n.next = n.next.next;
}
size--;
}
@Override
public void add(T t) throws Exception {
add(size,t);
}
@Override
public void set(int index, T t) throws Exception {
Node node = getNode(index);
node.item = t;
}
private Node getNode(int index) throws Exception {
if (index<0 || index > this.size-1){
throw new Exception("數組越界");
}
Node n = header.next;
for (int i = 0;i<index;i++){
n = n.next;
}
return n;
}
}在實際應用中雙鏈表的應用多一些，就比如LinkedList
雙鏈表的一個節點，有存儲數據的data，也有后驅節點next(指針)，指向下一個節點，這和單鏈表是一樣的，但它還有一個前驅節點pre(指針)，指向上一個節點。
這樣的設計，犧牲了額外的內存類存儲 “pre” 指針，但是相比單鏈表只能 “從頭向尾” 查找，雙鏈表不僅可以 “從頭向尾”，“從尾向頭”，甚至可以從中間開始查找，在有些時候，雙鏈表的查找效率要比單鏈表快很多。
這一點，在 JDK LinkedList 的源碼中有體現，我們來看它的 get(int index) 方法，
接著點進去，看它的 node(int index) 方法
如果 index 位于鏈表的前半部分，則從前開始查找；反之，則從后開始查找。
單鏈表查詢速度較慢，因為他需要從頭遍歷，插入刪除速度較快；內存利用率高，不會浪費內存，大小沒有固定，拓展很靈活
順序表查詢速度較快，插入刪除速度較慢
Java中的Arraylist和LinkedList就是兩種方式的代表，不過LinkedList使用雙向鏈表優化
雙鏈表的查詢速度要優于單鏈表
從存儲結構來看，每個雙鏈表的節點要比單鏈表的節點多一個指針，而長度為n就需要 n*length（這個指針的length在32位系統中是4字節，在64位系統中是8個字節） 的空間，這在一些追求時間效率不高應用下并不適應，因為它占用空間大于單鏈表所占用的空間；這時設計者就會采用以時間換空間的做法，這是一種工程總體上的衡量。
“什么是線性表、順序表、鏈表”的內容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業相關的知識可以關注億速云網站，小編將為大家輸出更多高質量的實用文章！
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
