數據結構（java版）學習筆記（一）——線性表

一、線性表的定義

線性表是n（n>=0）個具有相同特性的數據元素的有限序列。

線性表是最簡單、最常用的一種數據結構

線性表屬於線性結構的一種

如果一個數據元素序列滿足：

（1）除第一個和最後一個數據元素外，每個數據元素只有一個前驅數據元素和一個後繼數據元素；

（2）第一個數據元素沒有前驅數據元素；

（3）最後一個數據元素沒有後繼數據元素

則可以稱這樣的數據結構為線性結構

二、線性表的種類

線性表的存儲結構主要有兩種，順序存儲結構和鏈式存儲結構

用順序存儲結構的存放的線性表稱作為順序表，用鏈式存儲結構存放的線性表稱為線性鏈表

按照這個說法，之前所提到的java中的int數組等一維數組都是可以稱為順序表。

使用鏈式存儲結構，則會有前趨和後繼的說法

下列的圖可以說明一點（圖就這樣子了，別吐槽了。。）

A1作為開頭，所以沒有前趨，A1的後繼是A2

A2的前趨是A1，後繼則是A3

A3是末尾，所以沒有後繼，A3的前趨是A2

三、線性表的運算

基本運算都在圖中了，這裡就不多寫了，由於我們是使用java語言描述的，所以我們可將運算寫成一個介面（抽象類），之後再由類去實現此介面，覆寫這些方法，可能這樣說大家都不是很理解，沒有關係，在下一節就會使用到此介面了

public interface ListIntf {
    public int size(); //返回表的長度
    public void clear(); //重置表為空表
    public boolean isEmpty(); //判斷表是否為空
    public String get(int i); //取得表中第i個元素的值
    public int indexOf(String s);//獲得表中與數據元素s相等的第一個元素的位置（位序）
    public String getPre(String s);//獲得數據元素s的前趨
    public String getNext(String s);//獲得數據元素s的後繼
    public void insertElementAt(String s,int i);//在第i個位置之前插入新的數據元素s，表長度加1
    public String remove(int i);//刪除第i個數據元素，並返回其值，表長度減1
    public String remove(String s); //刪除數據元素s,並返回其值，表長度減1
}