柚子快報(bào)邀請(qǐng)碼778899分享：數(shù)據(jù)結(jié)構(gòu) 五分鐘“手撕”鏈表

http://yzkb.51969.com/

為了提高大家的學(xué)習(xí)效率，我把代碼放開(kāi)頭，供查閱。?

目錄

一、鏈表的實(shí)現(xiàn)代碼

二、什么是鏈表

三、鏈表的分類(lèi)

四、鏈表的常見(jiàn)操作

插入

刪除?

五、Java自帶的LinkedList?

?兩個(gè)構(gòu)造方法

?一些常用方法

六、LinkedList的遍歷

七、ArrayList和LinkedList的區(qū)別??

一、鏈表的實(shí)現(xiàn)代碼

//無(wú)頭單向鏈表

package demo1;

public class MySingleLinkedList{

class ListNode{

public int var;

public ListNode next;

public int val;

public ListNode(int var) {

this.var = var;

}

}

ListNode head;

public void creat(){

ListNode node1=new ListNode(1);

ListNode node2=new ListNode(1);

ListNode node3=new ListNode(1);

ListNode node4=new ListNode(1);

node1.next=node2;

node2.next=node3;

node3.next=node4;

head=node1;

}

//頭插法

public void addFirst(int data) {

ListNode node=new ListNode(data);

node.next=head;

head=node;

}

//尾插法

public void addLast(int data) {

ListNode node=new ListNode(data);

if(head==null){

head=node;

return;

}

ListNode cur=head;

while (cur.next!=null){

cur=cur.next;

}cur.next=node;

}

private void IndexCheck(int index)throws IndexNotLegal {

if(index<0||index>size()){

throw new IndexNotLegal("index位置不合法");

}

}

//任意位置插入,第一個(gè)數(shù)據(jù)節(jié)點(diǎn)為0號(hào)下標(biāo)

public void addIndex(int index, int data){

try {

IndexCheck(index);

}catch (IndexNotLegal e){

e.printStackTrace();

return;

}

ListNode node=new ListNode(data);

ListNode cur=head;

if(index==0){

addFirst(data);

return;

}if(index==size()){

addLast(data);

return;

}

//注意這里是index-1

for (int i = 0; i < index-1; i++) {

cur= cur.next;

}

node.next=cur.next;

cur.next=node;

}

//查找是否包含關(guān)鍵字key是否在單鏈表當(dāng)中

public boolean contains(int key) {

ListNode cur=head;

while (cur!=null){

if(cur.var==key){

return true;

}cur=cur.next;

}return false;

}

//刪除第一次出現(xiàn)關(guān)鍵字為key的節(jié)點(diǎn)

public void remove(int key) {

if(head.var==key){

head=head.next;

return;

}if(head==null){

return;

}

ListNode cur=head;

while (cur.next!=null){

if(cur.next.var==key){

cur.next=cur.next.next;

return;

}cur=cur.next;

}

}

//刪除所有出現(xiàn)的key節(jié)點(diǎn)

public void removeAllKey(int key) {

if(head==null){

return;

}ListNode prev=head;

ListNode cur=head.next;

while (cur!=null){

if(cur.var==key){

prev.next= cur.next;

//這里不能寫(xiě)prev=cur

cur= cur.next;

}else {

prev=cur;

cur= cur.next;

}

if(head.var==key){

head=head.next;

}

}

}

//得到單鏈表的長(zhǎng)度

public int size() {

ListNode cur=head;

int count=0;

while (cur!=null){

count++;

cur=cur.next;

}return count;

}

//打印鏈表

public void display() {

ListNode cur=head;

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

System.out.print(cur.var+" ");

cur=cur.next;

}

System.out.println();

}

//清除鏈表

public void clear() {

head=null;

}

}

public class IndexNotLegal extends RuntimeException {

public IndexNotLegal(){

}public IndexNotLegal(String s){

super(s);

}

}

package demo2;

// 無(wú)頭雙向鏈表

public class MyLinkedList {

class ListNode {

public int var;

ListNode prev;

ListNode next;

public ListNode(int var) {

this.var = var;

}

}

ListNode head;

ListNode last;

//頭插法

public void addFirst(int data) {

ListNode node = new ListNode(data);

if (head == null) {

head = last = node;

return;

}

node.next = head;

head.prev = node;

head = node;

}

//尾插法

public void addLast(int data) {

ListNode node = new ListNode(data);

if (head == null) {

head = last = node;

return;

}

last.next = node;

node.prev = last;

last = node;

}

private void indexCheck(int index) throws IndexNotLegal {

if (index < 0 || index > size()) {

throw new IndexNotLegal("index位置不合法");

}

}

private ListNode findIndexCur(int index) {

ListNode cur = head;

while (index != 0) {

cur = cur.next;

index--;

}

return cur;

}

//任意位置插入,第一個(gè)數(shù)據(jù)節(jié)點(diǎn)為0號(hào)下標(biāo)

public void addIndex(int index, int data) {

try {

indexCheck(index);

} catch (IndexNotLegal e) {

e.printStackTrace();

}

if (index == 0) {

addFirst(data);

return;

}

if (index == size()) {

addLast(data);

return;

}

ListNode node = new ListNode(data);

ListNode cur = findIndexCur(index);

//先把node插進(jìn)去，再調(diào)整node的前一個(gè)，最后再調(diào)cur，因?yàn)樾枰猚ur來(lái)調(diào)整

node.next=cur;

cur.prev.next=node;

node.prev=cur.prev;

cur.prev=node;

}

//查找是否包含關(guān)鍵字key是否在單鏈表當(dāng)中

public boolean contains(int key) {

ListNode cur = head;

while (cur != null) {

if (cur.var == key) {

return true;

}

cur = cur.next;

}

return false;

}

//刪除第一次出現(xiàn)關(guān)鍵字為key的節(jié)點(diǎn)

public void remove(int key) {

ListNode cur = head;

while (cur != null) {

if (cur.var == key) {

//頭節(jié)點(diǎn)

if (head.var == key) {

head.next.prev = null;

head = head.next;

return;

}

//尾巴節(jié)點(diǎn)

if (last.var == key) {

last.prev.next = null;

last = last.prev;

return;

}

cur.next.prev = cur.prev;

cur.prev.next = cur.next;

return;

}

cur = cur.next;

}

}

//刪除所有值為key的節(jié)點(diǎn)

public void removeAllKey(int key) {

ListNode cur = head;

while (cur != null) {

if (cur.var == key) {

//頭節(jié)點(diǎn)

if (head.var == key) {

head.next.prev = null;

head = head.next;

return;

}

//尾巴節(jié)點(diǎn)

if (last.var == key) {

last.prev.next = null;

last = last.prev;

return;

}

cur.next.prev = cur.prev;

cur.prev.next = cur.next;

}

cur = cur.next;

}

}

//得到單鏈表的長(zhǎng)度

public int size() {

int count = 0;

ListNode cur = head;

while (cur != null) {

cur = cur.next;

count++;

}

return count;

}

public void display() {

ListNode cur = head;

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

System.out.print(cur.var + " ");

cur = cur.next;

}

System.out.println();

}

public void clear() {

head = last = null;

}

}

package demo2;

public class IndexNotLegal extends RuntimeException{

public IndexNotLegal(){

}public IndexNotLegal(String s){

super(s);

}

}

二、什么是鏈表

簡(jiǎn)單來(lái)說(shuō)，像鏈子一樣的數(shù)據(jù)結(jié)構(gòu)。像火車(chē)一節(jié)一節(jié)車(chē)廂一樣，每個(gè)元素是獨(dú)立的個(gè)體（內(nèi)部類(lèi)）。 并且他們?cè)诳臻g里是分散的。?

?

為什么分散的還可以找到下一個(gè)呢？

答：一個(gè)節(jié)點(diǎn)里面裝著兩種東西，一個(gè)是值，一個(gè)的下一個(gè)的地址，這樣根據(jù)下一個(gè)的地址就可以找到下一個(gè)了。?

三、鏈表的分類(lèi)

常見(jiàn)的鏈表有三種，但是我這里只介紹兩種：無(wú)頭單鏈，無(wú)頭雙鏈。剩下的一種之后再補(bǔ)充。

單鏈和雙鏈的區(qū)別？

答： 一個(gè)節(jié)點(diǎn)都是一個(gè)類(lèi)。單鏈裝的是值和下個(gè)節(jié)點(diǎn)；雙鏈裝的是值和上個(gè)節(jié)點(diǎn)和下個(gè)節(jié)點(diǎn)

四、鏈表的常見(jiàn)操作

插入

怎么插入元素？在鏈表中很簡(jiǎn)單！?

單鏈：p下個(gè)節(jié)點(diǎn)改成n1，n0下個(gè)節(jié)點(diǎn)改為p。

雙鏈：?p下個(gè)節(jié)點(diǎn)改為n1，n0下個(gè)節(jié)點(diǎn)改為p（先把p插進(jìn)去，成一個(gè)逆時(shí)針），p上個(gè)節(jié)點(diǎn)改為n0，n1的上個(gè)節(jié)點(diǎn)改為p（修改原來(lái)的兩點(diǎn)節(jié)點(diǎn)）

注意！還需要考慮一些特殊情況，具體請(qǐng)看代碼的實(shí)現(xiàn)！

刪除?

在鏈表中刪除節(jié)點(diǎn)也非常方便，只需改變一個(gè)節(jié)點(diǎn)的引用（指針）即可。?

單鏈：n0的下個(gè)節(jié)點(diǎn)指向n1。

雙鏈：n0下個(gè)節(jié)點(diǎn)改為n1，n1上個(gè)節(jié)點(diǎn)改為n0?。

問(wèn)題來(lái)了：為什么p的指向n1可以不刪？

答;原因是以及沒(méi)人指向p了，?如果沒(méi)人引用（指向）的東西，就會(huì)被系統(tǒng)自動(dòng)回收。?像clear（）方法，head不指向首個(gè)節(jié)點(diǎn)，那么首個(gè)節(jié)點(diǎn)被回收，同理下面也如此。

五、Java自帶的LinkedList?

?兩個(gè)構(gòu)造方法

方法解釋LinkedList()無(wú)參構(gòu)造public LinkedList(Collection c)使用其他集合容器中元素構(gòu)造List

public static void main(String[] args) {

// 構(gòu)造一個(gè)空的LinkedList

List list1 = new LinkedList<>();

List list2 = new java.util.ArrayList<>();

list2.add("JavaSE");

list2.add("JavaWeb");

list2.add("JavaEE");

// 使用ArrayList構(gòu)造LinkedList

List list3 = new LinkedList<>(list2);

}

?一些常用方法

方法解釋boolean add(E e)尾插 evoid add(int index, E element)將 e 插入到 index 位置boolean addAll(Collection c)尾插 c 中的元素E remove(int index)刪除 index 位置元素boolean remove(Object o)刪除遇到的第一個(gè) oE get(int index)獲取下標(biāo) index 位置元素E set(int index, E element)將下標(biāo) index 位置元素設(shè)置為 elementvoid clear()清空boolean contains(Object o)判斷 o 是否在線性表中int indexOf(Object o)返回第一個(gè) o 所在下標(biāo)int lastIndexOf(Object o)返回最后一個(gè) o 的下標(biāo)List subList(int fromIndex, int toIndex)截取部分 list

public static void main(String[] args) {

LinkedList list = new LinkedList<>();

list.add(1); // add(elem): 表示尾插

list.add(2);

list.add(3);

list.add(4);

list.add(5);

list.add(6);

list.add(7);

System.out.println(list.size());

System.out.println(list);

// 在起始位置插入0

list.add(0, 0); // add(index, elem): 在index位置插入元素elem

System.out.println(list);

list.remove(); // remove(): 刪除第一個(gè)元素，內(nèi)部調(diào)用的是removeFirst()

list.removeFirst(); // removeFirst(): 刪除第一個(gè)元素

list.removeLast(); // removeLast(): 刪除最后元素

list.remove(1); // remove(index): 刪除index位置的元素

System.out.println(list);

// contains(elem): 檢測(cè)elem元素是否存在，如果存在返回true，否則返回false

if(!list.contains(1)){

list.add(0, 1);

}

list.add(1);

System.out.println(list);

System.out.println(list.indexOf(1)); // indexOf(elem): 從前往后找到第一個(gè)elem的位置

System.out.println(list.lastIndexOf(1)); // lastIndexOf(elem): 從后往前找第一個(gè)1的位置

int elem = list.get(0); // get(index): 獲取指定位置元素

list.set(0, 100); // set(index, elem): 將index位置的元素設(shè)置為elem

System.out.println(list);

// subList(from, to): 用list中[from, to)之間的元素構(gòu)造一個(gè)新的LinkedList返回

List copy = list.subList(0, 3);

System.out.println(list);

System.out.println(copy);

list.clear(); // 將list中元素清空

System.out.println(list.size());

}

六、LinkedList的遍歷

public static void main(String[] args) {

LinkedList list = new LinkedList<>();

list.add(1); // add(elem): 表示尾插

list.add(2);

list.add(3);

list.add(4);

list.add(5);

list.add(6);

list.add(7);

System.out.println(list.size());

//for循環(huán)遍歷

for (int i = 0; i < list.size(); i++) {

System.out.print(list.get(i)+" ");

}

// foreach遍歷

for (int e:list) {

System.out.print(e + " ");

}

System.out.println();

// 使用迭代器遍歷---正向遍歷

ListIterator it = list.listIterator();

while(it.hasNext()){

System.out.print(it.next()+ " ");

}

System.out.println();

// 使用反向迭代器---反向遍歷

ListIterator rit = list.listIterator(list.size());

while (rit.hasPrevious()){

System.out.print(rit.previous() +" ");

}

System.out.println();

}

七、ArrayList和LinkedList的區(qū)別??

不同點(diǎn)數(shù)組鏈表存儲(chǔ)方式連續(xù)內(nèi)存空間分散內(nèi)存空間容量擴(kuò)展長(zhǎng)度不可變可靈活擴(kuò)展內(nèi)存效率元素占用內(nèi)存少、但可能浪費(fèi)空間元素占用內(nèi)存多訪問(wèn)元素O(1)O(N)添加元素O(N)O(1)刪除元素O(N)O(1)

柚子快報(bào)邀請(qǐng)碼778899分享：數(shù)據(jù)結(jié)構(gòu) 五分鐘“手撕”鏈表

http://yzkb.51969.com/

好文推薦