2.1　線性表

2.1.1　線性表的定義

線性表是由N個相同數據類型的數據元素組成的有限序列，其中除了第一個數據元素外，每個元素有且僅有一個直接前驅結點，除最后一個數據元素外，每個元素有且僅有一個直接后繼結點。

線性表數據類型主要包括兩個方面：數據元素集合和該數據元素集合上的操作集合。

數據元素集合可以表示為A0,A1,A2,...,An-1大小為N的數據集合。

操作集合包括以下操作：

（1）向線性表插入元素。

（2）從線性表刪除元素。

（3）從線性表查找元素。

（4）判斷線性表是否為空。

（5）求線性表的元素個數。

2.1.2　線性表的類型

線性表是一種邏輯結構，這種邏輯結構在計算機中的表現形式（存儲結構）主要有以下兩種：

（1）線性存儲：用順序結構存儲的線性表叫作順序線性表，一般稱作順序表。順序表一般通過高級語言中的數組類型實現。

（2）鏈式存儲：用鏈式結構存儲的線性表叫作鏈式線性表，一般稱作鏈表。鏈表通常是通過定義結點的方式，通過指針（Java語言中使用的是引用）將各個數據元素和數據元素之間的關系體現出來的。

2.1.3　線性表的抽象類型的定義

由于線性表有順序表和鏈表兩種實現形式，因此可以通過軟件工程的設計思想對線性表這種數據結構進行抽象，由不同的子類生成不同的線性表的實現。

本節將定義一個List接口，該接口定義了線性表的規范，即定義線性表需要實現的基本操作，這些操作包括插入元素、刪除元素、查找元素、判斷表是否為空和查詢線性表元素個數。List接口代碼如下：

2.1.4　線性表常見面試考點

（1）線性表的概念。

（2）線性表的存儲方式和實現方式。

（3）在線性表中操作元素的時間復雜度。