一．介紹

鏈表是一種數(shù)據(jù)結(jié)構(gòu)，和數(shù)組同級。比如，Java中我們使用的ArrayList，其實(shí)現(xiàn)原理是數(shù)組。而LinkedList的實(shí)現(xiàn)原理就是鏈表了。鏈表在進(jìn)行循環(huán)遍歷時(shí)效率不高，但是插入和刪除時(shí)優(yōu)勢明顯。

鏈表是一種物理存儲單元上非連續(xù)、非順序的存儲結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過鏈表中的指針鏈接次序?qū)崿F(xiàn)的。鏈表由一系列結(jié)點(diǎn)（鏈表中每一個(gè)元素稱為結(jié)點(diǎn)）組成，結(jié)點(diǎn)可以在運(yùn)行時(shí)動態(tài)生成。每個(gè)結(jié)點(diǎn)包括兩個(gè)部分：一個(gè)是存儲數(shù)據(jù)元素的數(shù)據(jù)域，另一個(gè)是存儲下一個(gè)結(jié)點(diǎn)地址的指針域。 相比于線性表順序結(jié)構(gòu)，操作復(fù)雜。

二．知識點(diǎn)介紹

1、單向鏈表原理

2、LinkdList常用方法

3、雙端鏈表

4、有序鏈表

三．上課對應(yīng)視頻的說明文檔

1、單向鏈表原理

單向鏈表是一種線性表，實(shí)際上是由節(jié)點(diǎn)（Node）組成的，一個(gè)鏈表擁有不定數(shù)量的節(jié)點(diǎn)。其數(shù)據(jù)在內(nèi)存中存儲是不連續(xù)的，它存儲的數(shù)據(jù)分散在內(nèi)存中，每個(gè)結(jié)點(diǎn)只能也只有它能知道下一個(gè)結(jié)點(diǎn)的存儲位置。由N各節(jié)點(diǎn)（Node）組成單向鏈表，每一個(gè)Node記錄本Node的數(shù)據(jù)及下一個(gè)Node。向外暴露的只有一個(gè)頭節(jié)點(diǎn)（Head），我們對鏈表的所有操作，都是直接或者間接地通過其頭節(jié)點(diǎn)來進(jìn)行的。

上圖中最左邊的節(jié)點(diǎn)即為頭結(jié)點(diǎn)（Head），但是添加節(jié)點(diǎn)的順序是從右向左的，添加的新節(jié)點(diǎn)會被作為新節(jié)點(diǎn)。最先添加的節(jié)點(diǎn)對下一節(jié)點(diǎn)的引用可以為空。引用是引用下一個(gè)節(jié)點(diǎn)而非下一個(gè)節(jié)點(diǎn)的對象。因?yàn)橛兄粩嗟囊?，所以頭節(jié)點(diǎn)就可以操作所有節(jié)點(diǎn)了。

下圖描述了單向鏈表存儲情況。存儲是分散的，每一個(gè)節(jié)點(diǎn)只要記錄下一節(jié)點(diǎn)，就把所有數(shù)據(jù)串了起來，形成了一個(gè)單向鏈表。

節(jié)點(diǎn)（Node）是由一個(gè)需要儲存的對象及對下一個(gè)節(jié)點(diǎn)的引用組成的。也就是說，節(jié)點(diǎn)擁有兩個(gè)成員：儲存的對象、對下一個(gè)節(jié)點(diǎn)的引用。下面圖是具體的說明：

2、LinkedList常用方法

（1） 鏈表LinkedList是由若干個(gè)稱為結(jié)點(diǎn)的對象組成的一種數(shù)據(jù)結(jié)構(gòu)，每個(gè)結(jié)點(diǎn)含有一個(gè)數(shù)據(jù)和下一個(gè)結(jié)點(diǎn)的引用，或含有一個(gè)數(shù)據(jù)并含有上一個(gè)結(jié)點(diǎn)的引用和下一個(gè)結(jié)點(diǎn)的引用。

（2） 常用方法

public boolean add(Object o)：向鏈表添加一個(gè)新的結(jié)點(diǎn)o(只能向鏈表中添加對象，不能添加某個(gè)基本數(shù)據(jù)類型的數(shù))

public void add(int index,Object o)：向鏈表的指定位置index處添加一個(gè)新的結(jié)點(diǎn)o

public void addFirst(Object o)：向鏈表的頭添加新的結(jié)點(diǎn)o

public void addLast(Object o)：向鏈表的末尾添加新的結(jié)點(diǎn)o

public void clear()：刪除鏈表的所有結(jié)點(diǎn)，使當(dāng)前鏈表成為空鏈表

public Object remove(int index)：刪除指定位置index上的結(jié)點(diǎn)

public boolean remove(Object o)：刪除首次出現(xiàn)含有數(shù)據(jù)o的結(jié)點(diǎn)

public Object removeFirst()：刪除第一個(gè)結(jié)點(diǎn)，并返回這個(gè)結(jié)點(diǎn)中的對象

public Object removeLast()：刪除最后一個(gè)結(jié)點(diǎn)，并返回這個(gè)結(jié)點(diǎn)中的對象

public Object get(int index)：獲取鏈表中指定位置index處結(jié)點(diǎn)中的對象

public Object getFirst()：獲取鏈表中第一個(gè)結(jié)點(diǎn)中的對象

public Object getLast()：獲取鏈表中最后一個(gè)結(jié)點(diǎn)中的對象

public int indexOf(Object o)：返回含有數(shù)據(jù)o的結(jié)點(diǎn)在鏈表中首次出現(xiàn)的位置，如果鏈表中無此結(jié)點(diǎn)，則返回-1

public int lastIndexOf(Object o)：返回含有數(shù)據(jù)o的結(jié)點(diǎn)在鏈表中最后出現(xiàn)的位置，如果鏈表中無此結(jié)點(diǎn)，則返回-1

public Object set(int index,Object o)：將當(dāng)前鏈表index位置結(jié)點(diǎn)中的對象替換為參數(shù)o指定的對象，并返回被替換的對象

public int size()：返回鏈表的長度，即結(jié)點(diǎn)的個(gè)數(shù)

public boolean contains(Object o)：判斷鏈表結(jié)點(diǎn)中是否有結(jié)點(diǎn)含有對象o

案例1：

import java.util.*;

public class LLTest{

public static void main(String args[]){

LinkedList l=new LinkedList();

for(int i=0;i<=5;i++){

l.add("a"+i);

}

l.add(3,"a100");? //添加

System.out.println(l);

l.set(6,"a200");? //更改

System.out.println(l);

System.out.println(l.get(2));? //獲取值

System.out.println(l.indexOf("a3"));? //下標(biāo)

l.remove(1);? ? //移除

System.out.println(l);

System.out.println(l.indexOf("a3"));

}

}

案例2：

import java.util.*;

public class LLTest2{

public static void main(String args[]){

LinkedList l=new LinkedList();

l.add("a1");

l.add("a2");

System.out.println(l);

l.addFirst("a100"); //添加到頭

l.addLast("a200");? //添加到尾

System.out.println(l);

System.out.println(l.getFirst());? //獲取頭

System.out.println(l.getLast());? ? //獲取尾

l.removeFirst();? ? //移除頭

l.removeLast(); //移除尾

System.out.println(l);

}

}

案例：單項(xiàng)鏈表

public class LinkedList {?

//聲明一個(gè)內(nèi)部類

private class Data{?

private Object obj;?

private Data next = null;?

Data(Object obj){?

this.obj = obj;?

}?

}?

private Data first = null;?

//加入元素對象

public void insertFirst(Object obj){?

Data data = new Data(obj);?

data.next = first;?

first = data;?

}?

//刪除元素對象

public Object deleteFirst() throws Exception{?

if(first == null)?

throw new Exception("empty!");?

Data temp = first;?

first = first.next;?

return temp.obj;?

}?

//查看對象元素

public Object find(Object obj) throws Exception{?

if(first == null)?

throw new Exception("LinkedList is empty!");?

Data cur = first;?

while(cur != null){?

if(cur.obj.equals(obj)){?

return cur.obj;?

}?

cur = cur.next;?

}?

return null;?

}?

//移出對象

public void remove(Object obj) throws Exception{?

if(first == null)?

throw new Exception("LinkedList is empty!");?

if(first.obj.equals(obj)){?

first = first.next;?

}else{?

Data pre = first;?

Data cur = first.next;?

while(cur != null){?

if(cur.obj.equals(obj)){?

pre.next = cur.next;?

}?

pre = cur;?

cur = cur.next;?

}?

}?

}?

//判斷是否有對象

public boolean isEmpty(){?

return (first == null);?

}?

//顯示對象

public void display(){?

if(first == null)?

System.out.println("empty");?

Data cur = first;?

while(cur != null){?

System.out.print(cur.obj.toString() + " -> ");?

cur = cur.next;?

}?

System.out.print("\n");?

}?

public static void main(String[] args) throws Exception {?

LinkedList ll = new LinkedList();?

ll.insertFirst(4);?

ll.insertFirst(3);?

ll.insertFirst(2);?

ll.insertFirst(1);?

ll.display();?

ll.deleteFirst();?

ll.display();?

ll.remove(3);?

ll.display();?

System.out.println(ll.find(1));?

System.out.println(ll.find(4));?

}?

}

3、雙端鏈表

雙端鏈表(不是雙向鏈表)：與單向鏈表的不同之處在保存有對最后一個(gè)鏈接點(diǎn)的引用(last)

案例：

public class FirstLastList {?

private class Data{?

private Object obj;?

private Data next = null;?

Data(Object obj){?

this.obj = obj;?

}?

}?

private Data first = null;?

private Data last = null;?

//插入對象

public void insertFirst(Object obj){?

Data data = new Data(obj);?

if(first == null)?

last = data;?

data.next = first;?

first = data;?

}?

//尾部插入對象

public void insertLast(Object obj){?

Data data = new Data(obj);?

if(first == null){?

first = data;?

}else{?

last.next = data;?

}?

last = data;?

}?

//刪除頭部第一個(gè)對象

public Object deleteFirst() throws Exception{?

if(first == null)?

throw new Exception("empty");?

Data temp = first;?

if(first.next == null)?

last = null;?

first = first.next;?

return temp.obj;?

}? ?

//刪除最后一個(gè)對象

public void deleteLast() throws Exception{?

if(first == null)?

throw new Exception("empty");?

if(first.next == null){?

first = null;?

last = null;?

}else{?

Data temp = first;?

while(temp.next != null){?

if(temp.next == last){?

last = temp;?

last.next = null;?

break;?

}?

temp = temp.next;?

}?

}?

}?

//顯示對象

public void display(){?

if(first == null)?

System.out.println("empty");?

Data cur = first;?

while(cur != null){?

System.out.print(cur.obj.toString() + " -> ");?

cur = cur.next;?

}?

System.out.print("\n");?

}?

public static void main(String[] args) throws Exception {?

FirstLastList fll = new FirstLastList();?

fll.insertFirst(2);?

fll.insertFirst(1);?

fll.display();?

fll.insertLast(3);?

fll.display();?

fll.deleteFirst();?

fll.display();?

fll.deleteLast();?

fll.display();?

}?

}?

4、有序鏈表

有序鏈表：鏈表中的數(shù)據(jù)按從小到大排列

案例：

public class SortedList {?

private class Data{?

private Object obj;?

private Data next = null;?

Data(Object obj){?

this.obj = obj;?

}?

}?

private Data first = null;?

//插入對象

public void insert(Object obj){?

Data data = new Data(obj);?

Data pre = null;?

Data cur = first;?

while(cur != null && (Integer.valueOf(data.obj.toString())?

.intValue() > Integer.valueOf(cur.obj.toString())?

.intValue())){?

pre = cur;?

cur = cur.next;?

}?

if(pre == null)?

first = data;?

else?

pre.next = data;?

data.next = cur;?

}?

//刪除對象

public Object deleteFirst() throws Exception{?

if(first == null)?

throw new Exception("empty!");?

Data temp = first;?

first = first.next;?

return temp.obj;?

}?

//顯示對象

public void display(){?

if(first == null)?

System.out.println("empty");?

System.out.print("first -> last : ");?

Data cur = first;?

while(cur != null){?

System.out.print(cur.obj.toString() + " -> ");?

cur = cur.next;?

}?

System.out.print("\n");?

}?

public static void main(String[] args) throws Exception{?

SortedList sl = new SortedList();?

sl.insert(80);?

sl.insert(2);?

sl.insert(100);?

sl.display();?

System.out.println(sl.deleteFirst());?

sl.insert(33);?

sl.display();?

sl.insert(99);?

sl.display();?

}?

}?