點個贊，看一看，好習慣！本文 GitHub https://github.com/OUYANGSIHAI/JavaInterview 已收錄，這是我花了 3 個月總結的一線大廠 Java 面試總結，本人已拿大廠 offer。
另外，原創文章首發在我的個人博客：blog.ouyangsihai.cn，歡迎訪問。

一、線性表

一個線性表（Linear List）是由n(n≥0)個數據元素（結點，它可以是一個字母，數字，記錄或更復雜的信息）所構成的有限序列。線性表邏輯地表示為：（a0,a1,…,an-1)。其中，n為線性表的長度，n=0時為空表。稱i為ai在線性表中的位序號。

然后，我們對順序存儲結構用圖來做一個理解。

1.1 順序存儲結構理解

順序儲存結構是用數組來保存數據的。如下圖：

說明：線性表也就是數組的一種特殊儲存方式：從頭到尾依次儲存數據。

下面這種情況就不是線性表：

1.2 插入數據

1. 線性表為空的情況

很簡單，當線性表為空時，將數據放到0的位置上就可以了

2. 插入到末尾

說明：1和2是一種情況，都是將數據直接添加到線性表的末尾。

3. 一般情況

說明：簡單來理解，就是騰出地方，然后插入,即：將要插入的位置的元素的位置之后的元素往后移動一個位置。

1.3 移除數據

1. 末尾的數據移除

說明：很簡單，直接置空就可以了。

2.一般情況

說明：跟插入的一般操作相反，先移除，再把坑填上,即：把后面的元素往前移動一個位置。

看完上面的理解之后，我們再來看java的具體實現，這個也是ArrayList的實現方式。

二、線性表的抽象數據類型

首先，我們給出線性表ode抽象數據類型。

1、線性表的置空操作：clear()

2、線性表判空操作：	isEmpty()
3、求線性表的長度：	length( )
4、取元素操作：	get( i )
5、插入操作：	insert( i, x )
6、刪除操作：	remove( i)
7、查找操作：	indexOf(x )
8、輸出操作：	display()

線性表抽象數據類型的Java接口描述：

public interface IList { public void clear(); // 將一個已經存在的線性表置成空表 public boolean isEmpty(); // 判斷當前線性表中的數據元素個數是否為0,若為0則函數返回true，否則返回false public int length(); // 求線性表中的數據元素個數并由函數返回其值 public Object get(int i) throws Exception;// 讀取到線性表中的第i個數據元素并由函數返回其值。其中i取值范圍為：0≤i≤length()-1,如果i值不在此范圍則拋出異常 public void insert(int i, Object x) throws Exception;// 在線性表的第i個數據元素之前插入一個值為x的數據元素。其中i取值范圍為：0≤i≤length()。如果i值不在此范圍則拋出異常,當i=0時表示在表頭插入一個數據元素x,當i=length()時表示在表尾插入一個數據元素x public void remove(int i) throws Exception;// 將線性表中第i個數據元素刪除。其中i取值范圍為：0≤i≤length()- 1,如果i值不在此范圍則拋出異常 public int indexOf(Object x);// 返回線性表中首次出現指定元素的索引，如果列表不包含此元素，則返回 -1 public void display();// 輸出線性表中的數據元素 }

三、線性表的順序存儲

線性表它包括順序表，鏈式表，這篇文章先介紹介紹順序表。

1、概念

順序存儲指用一組地址連續的存儲單元 依次存放 線性表中的數據元素的存儲結構。用順序存儲的線性表就稱為順序表，所有數據元素的存儲位置均取決于第一個數據元素的存儲位置。

2、特點

• 邏輯上相鄰的數據元素，賦以相鄰的存儲位置；

• 存儲密度高；

• 便于隨機存取；

• 不便于插入、刪除操作。

好了，看完啦這些基本的概念之后，相信小伙伴們對于線性表的順序存儲肯定有了一定的了解，如果學過數據結構的小伙伴，那就更不用說了，下面我們自己動手寫一個順序表的接口。

3、順序表接口的描述

public class SqList implements IList { private Object[] listElem; // 線性表存儲空間 private int curLen; // 當前長度 // 順序表的構造函數，構造一個存儲空間容量為maxSize的線性表 public SqList(int maxSize) { curLen = 0; // 置順序表的當前長度為0 listElem = new Object[maxSize];// 為順序表分配maxSize個存儲單元 } // 將一個已經存在的線性表置成空表 public void clear() { curLen = 0; // 置順序表的當前長度為0 } // 判斷當前線性表中數據元素個數是否為0,若為0則函數返回true，否則返回false public boolean isEmpty() { return curLen == 0; } // 求線性表中的數據元素個數并由函數返回其值 public int length() { return curLen; // 返回順序表的當前長度 } // 讀取到線性表中的第i個數據元素并由函數返回其值。其中i取值范圍為：0≤i≤length()-1,如果i值不在此范圍則拋出異常 public Object get(int i) throws Exception { if (i < 0 || i > curLen - 1) // i小于0或者大于表長減1 throw new Exception("第" + i + "個元素不存在"); // 輸出異常 return listElem[i]; // 返回順序表中第i個數據元素 } // 在線性表的第i個數據元素之前插入一個值為x的數據元素。其中i取值范圍為：0≤i≤length()。如果i值不在此范圍則拋出異常,當i=0時表示在表頭插入一個數據元素x,當i=length()時表示在表尾插入一個數據元素x public void insert(int i, Object x) throws Exception { if (curLen == listElem.length) // 判斷順序表是否已滿 throw new Exception("順序表已滿");// 輸出異常 if (i < 0 || i > curLen) // i小于0或者大于表長 throw new Exception("插入位置不合理");// 輸出異常 for (int j = curLen; j > i; j--) listElem[j] = listElem[j - 1];// 插入位置及之后的元素后移 listElem[i] = x; // 插入x curLen++;// 表長度增1 } // 將線性表中第i個數據元素刪除。其中i取值范圍為：0≤i≤length()- 1,如果i值不在此范圍則拋出異常 public void remove(int i) throws Exception { if (i < 0 || i > curLen - 1) // i小于1或者大于表長減1 throw new Exception("刪除位置不合理");// 輸出異常 for (int j = i; j < curLen - 1; j++) listElem[j] = listElem[j + 1];// 被刪除元素之后的元素左移 curLen--; // 表長度減1 } // 返回線性表中首次出現指定元素的索引，如果列表不包含此元素，則返回 -1 public int indexOf(Object x) { int j = 0;// j為計數器 while (j < curLen && !listElem[j].equals(x)) // 從順序表中的首結點開始查找，直到listElem[j]指向元素x或到達順序表的表尾 j++; if (j < curLen)// 判斷j的位置是否位于表中 return j; // 返回x元素在順序表中的位置 else return -1;// x元素不在順序表中 } // 輸出線性表中的數據元素 public void display() { for (int j = 0; j < curLen; j++) System.out.print(listElem[j] + " "); System.out.println();// 換行 } }

上面我們基本上實現了java版的線性表，但是，有一個問題就是我們的數據只能是int，因此，在上面的基礎上，我們再對數據類型進行泛型化。

public class SequenceList<T>{//默認長度private int DEFAULT_SIZE = 2;//定義一個數組用于保存線性表的長度private Object[] elementData;//用于保存數組長度private int capacity;//保存順序表中當前元素的個數private int size = 0;/*** 構造一個默認長度的空線性表*/public SequenceList(){capacity = DEFAULT_SIZE;elementData = new Object[capacity];}/*** 用一個初始化元素來創建線性表* @param element 初始化元素*/public SequenceList(T element){this();elementData[0] = element;size++;}/*** 用一個元素和指定長度來創建線性表* @param element 元素* @param initSize 指定長度*/public SequenceList(T element,int initSize){capacity = 1;if(capacity<initSize){capacity = initSize +2;}elementData = new Object[capacity];elementData[0] = element;size++;}/*** 向順序表中插入元素* @param element 待插入的元素* @param index 待插入的位置*/public void insert(T element,int index){if(index<0||index>size){throw new IndexOutOfBoundsException("數組越界異常");}ensureCapacity(size+1);//把index以后的元素都后移一位System.arraycopy(elementData, index, elementData, index+1, size-index);elementData[index] = element; size++;}/*** 表長* @return*/public int length(){return size;}/*** 向表中添加元素* @param element*/public void add(T element){insert(element, size);}/*** 得到線性表存儲的對象* @param index 獲得的位置* @return 得到的結果*/public T get(int index){if(index<0||index>size)throw new IndexOutOfBoundsException("數組越界異常");return (T)elementData[index];}/*** 判斷線性表是否為空* @return*/public boolean isEmpty(){return size==0;}/*** 清空線性表*/public void clear(){Arrays.fill(elementData, null);size = 0;}/*** 獲取指定位置的前一個元素* @param index 線性表位置，若是取線性表最后一個元素，必須index = size,* size為線性表元素個數* @return */public T priorElem(int index){if(index>0&&index<size+1)return (T)elementData[index-1];else {throw new IndexOutOfBoundsException("數組越界異常");}}/*** 刪除指定位置的元素* @param index*/public void delete(int index){if(index<0||index>size-1){throw new IndexOutOfBoundsException("數組越界異常");}else{//把數組前移一位System.arraycopy(elementData, index+1, elementData, index, size-index-1);size--;//清空最后一個元素elementData[size]=null;}}/*** 獲取指定線性表位置的后一個元素* @param index 線性表位置，若是取線性表第0個元素，必須index=-1* @return*/public T nextElem(int index){if (index==-1) {return (T)elementData[0];}else if (index<size-1&&index>-1) {return (T)elementData[index+1];}else{throw new IndexOutOfBoundsException("數組越界異常");}}/*** 確保數組所需長度大于數組原有長度* @param mCapacity 數組所需長度*/private void ensureCapacity(int mCapacity){if(mCapacity>capacity){capacity=mCapacity+2; // System.out.println("capacity:"+capacity);elementData = Arrays.copyOf(elementData, capacity);}} }

這個代碼是不是簡潔多了，這個也是比較接近ArrayList的源碼。

我相信，通過上面的介紹，然后小伙伴們把這些代碼敲幾遍，記住一定要敲出來，這樣才能夠體會。如果你這樣做了，我相信這個你肯定能夠掌握了，下面我們做一個線性表的應用。

四、順序表應用舉例：

編寫一個順序表類的成員函數，實現對順序表循環右移k位的操作。即原來順序表為（a1,a2,…,an-k,an-k+1,…, an），循環向右移動k位后變成（an-k+1,…, an ,a1,a2,…,an-k）。要求時間復雜度為O（n）。

1、編寫一個順序表類的成員函數，實現對順序表循環右移k位的操作（函數如下）。在上面SqList類中加上下面函數，

public void shit(int k) { int n=curLen,p=0,i,j,l; Object temp; for(i=1;i<=k;i++) if(n%i==0&&k%i==0) //求n和k的最大公約數p p=i; for(i=0;i<p;i++){ j=i; l=(i+n-k)%n; temp=listElem[i]; while(l!=i){ listElem[j]=listElem[l]; j=l; l=(j+n-k)%n; }// 循環右移一步 listElem[j]=temp; } }

2、然后我們測試一下

public class Result { public static void main(String[] args) throws Exception { SqList L = new SqList(10); for (int i = 0; i <= 8; i++) L.insert(i, i); System.out.println("右移前順序表中的各個數據元素為："); L.display(); L.shit(3); System.out.println("右移3位后順序表中的各個數據元素為："); L.display(); } }

結果：
右移前順序表中的各個數據元素為：
0 1 2 3 4 5 6 7 8
右移3位后順序表中的各個數據元素為：
6 7 8 0 1 2 3 4 5

注意：如果上面的講解還有什么疑問的話，歡迎小伙伴們在留言區留言和大家一起探討學習。

點個贊，看一看，好習慣！本文 GitHub https://github.com/OUYANGSIHAI/JavaInterview 已收錄，這是我花了 3 個月總結的一線大廠 Java 面試總結，本人已拿大廠 offer。
另外，原創文章首發在我的個人博客：blog.ouyangsihai.cn，歡迎訪問。

最后，再分享我歷時三個月總結的 Java 面試 + Java 后端技術學習指南，這是本人這幾年及春招的總結，已經拿到了大廠 offer，整理成了一本電子書，拿去不謝，目錄如下：

現在免費分享大家，在下面我的公眾號 程序員的技術圈子 回復 面試 即可獲取。

有收獲？希望老鐵們來個三連擊，給更多的人看到這篇文章

1、老鐵們，關注我的原創微信公眾號「程序員的技術圈子」，專注于 Java、數據結構和算法、微服務、中間件等技術分享，保證你看完有所收獲。

2、給俺點個贊唄，可以讓更多的人看到這篇文章，順便激勵下我繼續寫作，嘻嘻。

3、另外，原創文章首發在我的個人博客：blog.ouyangsihai.cn，歡迎訪問。

點贊是對我最大的鼓勵
↓↓↓↓↓↓

總結

以上是生活随笔為你收集整理的数据结构：线性表（java实现）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。