什么是線性表？
? 線性表（Linear List），是由同類型數(shù)據(jù)元素構(gòu)成有序序列的線性結(jié)構(gòu)，表中元素個(gè)數(shù)稱為線性表的長(zhǎng)度；線性表沒有元素時(shí)，稱為空表；表的起始位置稱為表頭，表的結(jié)束位置稱為表尾。
抽象數(shù)據(jù)類型描述
? 類型名稱：線性表（List）
? 數(shù)據(jù)對(duì)象集：線性表是n（n>=0）個(gè)元素構(gòu)成的有序序列（a,a2,...,an）
? 操作集：Item 表示元素類型，整數(shù) i 表示位置
-
boolean isEmpty()線性表是否為空 -
int size()線性表中的元素個(gè)數(shù) -
void insert(Item item, int i)在 i 位置插入元素 -
void delete(int i)在第i個(gè)位置刪除數(shù)據(jù)(即刪除數(shù)組下標(biāo)為i-1這個(gè)位置) -
int find(Item item)查找某個(gè)元素，如果找到，返回下標(biāo)；否則返回-1
順序存儲(chǔ)實(shí)現(xiàn)（固定大?。?/h3>
? 創(chuàng)建一個(gè)泛型類List：
public class List<Item>{
private Item[] data; // 泛型數(shù)組存儲(chǔ)數(shù)據(jù)
private int last = -1; // last表示最后一個(gè)元素的下標(biāo)
}
? 構(gòu)造函數(shù)：
public List(int size){
data = (Item[]) new Object[size]; // java不允許創(chuàng)建泛型數(shù)組，所以需要用到類型轉(zhuǎn)換
}
插入數(shù)據(jù)
? 在這里，我們插入數(shù)據(jù)的位置范圍是1n+1，即第一個(gè)位置到最后一個(gè)位置+1（這里的n就表示當(dāng)前List中的元素個(gè)數(shù)）。所以我們就會(huì)發(fā)現(xiàn)我們?cè)诓迦霐?shù)據(jù)后，這些數(shù)據(jù)都是連續(xù)的。比如：在創(chuàng)建了List之后，數(shù)組中沒有元素，元素個(gè)數(shù)為0，那么此時(shí)插入的范圍就是10+1，只有1這個(gè)位置可以插入，之后再插入第二個(gè)元素，這時(shí)元素的個(gè)數(shù)已經(jīng)變成了1，此時(shí)的范圍是1~1+1，以此類推，存儲(chǔ)在這個(gè)線性表中的數(shù)據(jù)總會(huì)是連續(xù)的。
? 當(dāng)我們向線性表中插入數(shù)據(jù)時(shí)，首先要看看這個(gè)線性表滿了沒有，如果滿了不能插入，判斷滿的條件就是：last==data.length-1如果最后一個(gè)元素的下標(biāo)等于數(shù)組的最后一個(gè)下標(biāo)，說明滿了。
? 然后，要判斷插入的位置是否合法：i < 1 || i > last+2(n+1 >= i >= 1)。
? 之前說過，List中存儲(chǔ)的數(shù)據(jù)是連續(xù)的，所以我們插入時(shí)不能直接插入，需要將元素往后挪出一個(gè)空位才能夠在特定的位置進(jìn)行插入：
// 挪動(dòng)的順序毫無疑問是從最后一個(gè)元素挪，否則你從第i個(gè)元素挪的話就會(huì)覆蓋掉后面的元素
for (int j=last; j>=i-1; j--){
data[j+1] = data[j];
}
// 插入數(shù)據(jù)
data[i-1] = item;
// last加1
last = last + 1;
刪除元素
? 和插入元素類似，只是挪動(dòng)元素是往前挪動(dòng)元素，填補(bǔ)刪除后留下的空位。直接上代碼：
// 如果List空，不能刪除
if (isEmpty()){
System.out.println("List為空，不能刪除");
}
// 規(guī)定的刪除位置在1~n+1
if (i < 1 || i > last+2){
System.out.println("刪除位置非法，無法插入!");
}
// 在刪除之后需要先將數(shù)據(jù)往前挪
for (int j=i-1; j<last; j++){
data[j] = data[j+1];
}
last = last - 1;
完整代碼：
public class List<Item> {
// Java不允許創(chuàng)建泛型數(shù)組，所以做強(qiáng)制類型轉(zhuǎn)換
private Item[] data;
private int last = -1; // 表示List中最后一個(gè)元素的下標(biāo)
// 構(gòu)造函數(shù)-創(chuàng)建List時(shí)指定大小
public List(int size){
data = (Item[]) new Object[size];
}
// List是否為空
public boolean isEmpty(){
return last==-1;
}
// 返回List的大小
public int size(){
return last+1;
}
// 在第i個(gè)位置插入數(shù)據(jù)(即插入到數(shù)組下標(biāo)為i-1這個(gè)位置)
public void insert(Item item, int i){
// 如果List滿了，不能插入
if (last==data.length-1){
System.out.println("數(shù)組滿，無法插入!");
}
// 規(guī)定的插入位置在1~n+1之間
if (i < 1 || i > last+2){
System.out.println("插入位置非法，無法插入!");
}
// 在插入之前需要先將數(shù)據(jù)往后挪
for (int j=last; j>=i-1; j--){
data[j+1] = data[j];
}
data[i-1] = item;
last = last + 1;
}
// 在第i個(gè)位置刪除數(shù)據(jù)(即刪除數(shù)組下標(biāo)為i-1這個(gè)位置)
public void delete(int i){
// 如果List空，不能刪除
if (isEmpty()){
System.out.println("List為空，不能刪除");
}
// 規(guī)定的刪除位置在1~n+1
if (i < 1 || i > last+2){
System.out.println("刪除位置非法，無法插入!");
}
// 在刪除之后需要先將數(shù)據(jù)往前挪
for (int j=i-1; j<last; j++){
data[j] = data[j+1];
}
last = last - 1;
}
// 查找某個(gè)元素，如果查找到，返回下標(biāo)，否則返回-1
public int find(Item item){
for (int i=0; i<last+1; i++){
if (data[i]==item){
return i;
}
}
return -1;
}
public void printData(){
for (Item item:data){
System.out.print(" " + item);
}
System.out.println("");
}
// 測(cè)試
public static void main(String[] args) {
List<Integer> testList = new List(5);
testList.insert(1,1);
testList.insert(2,2);
testList.insert(3,3);
testList.insert(4,4);
testList.insert(5,5);
testList.printData();
testList.delete(1);
testList.printData();
System.out.println(testList.find(3));
}
}
鏈?zhǔn)酱鎯?chǔ)實(shí)現(xiàn)
? 創(chuàng)建一個(gè)泛型類 LinkedList：
public class LinkedList<Item> {
private Node head; // 線性表的表頭（鏈表的入口）
private int N; // 結(jié)點(diǎn)的數(shù)量（線性表中的元素?cái)?shù)量）
// node結(jié)點(diǎn)類
private class Node{
Item item;
Node next;
// 構(gòu)造器
public Node(Item item, Node next) {
this.item = item;
this.next = next;
}
}
}
? 求線性表的長(zhǎng)度和是否為空：
public int length(){
return N;
}
public boolean isEmpty(){
return head==null; // 當(dāng)head為null或N為0
}
? 查找相應(yīng)的位置的結(jié)點(diǎn)：
public Node findXth(int X){
Node temp = head;
int i = 1;
// 當(dāng)當(dāng)前結(jié)點(diǎn)不為空且位置小于X時(shí)
while (temp != null && i < X){
temp = temp.next;
i = i+1;
}
// 跳出循環(huán)有兩種可能，當(dāng)前結(jié)點(diǎn)為空或i==X
if (i == X){
return temp;
} else{
return null;
}
}
插入數(shù)據(jù)
? 因?yàn)槭擎準(zhǔn)酱鎯?chǔ)，所以不必關(guān)心空間的問題，只需care插入問題。
? 要向鏈表中插入結(jié)點(diǎn)，首先要分插入的位置。如果是插到鏈表的頭，需要做特殊處理：讓插入結(jié)點(diǎn)的next的值變?yōu)閔ead，head的值置為新插入的結(jié)點(diǎn)；如果插入到其他位置，只需要先找到插入位置的前一個(gè)結(jié)點(diǎn)p，然后是兩步（順序不能更改）：1、設(shè)置插入的結(jié)點(diǎn)的next的值為p的next。2、改變p的next的值為插入的結(jié)點(diǎn)。
public void insert(int i, Item item){
Node temp, p;
if (i == 1){
temp = new Node(item, head);
head = temp;
N = N+1;
return;
}
p = findXth(i-1);
if (p == null){
System.out.println("參數(shù)i錯(cuò)誤!");
return;
} else{
temp = new Node(item, p.next);
p.next = temp;
N = N+1;
return;
}
}
刪除數(shù)據(jù)
? 和插入類似，區(qū)分刪除的是頭結(jié)點(diǎn)還是其他位置，刪除頭結(jié)點(diǎn)：只需head置為head的next；刪除其他結(jié)點(diǎn)：找到前一個(gè)結(jié)點(diǎn)p，使其next置為p.next.next即可，java會(huì)自動(dòng)進(jìn)行垃圾回收。
public void delete(int i){
Node p;
if (i == 1){
if (head == null){
System.out.println("鏈表為空!");
return;
} else{
head = head.next;
N = N-1;
return;
}
}
p = findXth(i-1);
if (p == null || p.next == null){
System.out.println("第i個(gè)結(jié)點(diǎn)不存在!");
} else {
p.next = p.next.next;
N = N-1;
}
}
