?博主主頁: 33的博客?
??文章專欄分類:數(shù)據(jù)結(jié)構(gòu)??
??我的代碼倉庫: 33的代碼倉庫??
??????關(guān)注我?guī)銓W(xué)更多數(shù)據(jù)結(jié)構(gòu)知識

1. 前言

在上一篇文章中，我們已經(jīng)認(rèn)識了順序表，通過源碼我們知道ArrayList底層是使用數(shù)組來存儲元素，當(dāng)在ArrayList任意位置插入或者刪除元素時，就需要將后序元素整體往前或者往后搬移，時間復(fù)雜度為O(n)，效率比較低，因此ArrayList不適合做任意位置插入和刪除比較多的場景。因此：java集合中又引入了LinkedList，即鏈表結(jié)構(gòu)。

2.鏈表

鏈表是一種物理存儲結(jié)構(gòu)上非連續(xù)存儲結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過鏈表中的引用鏈接次序?qū)崿F(xiàn)的 。


注意： 鏈?zhǔn)浇Y(jié)構(gòu)是在邏輯上連續(xù)，但在物理上不一定連續(xù)。

實際中鏈表的結(jié)構(gòu)非常多樣，以下情況組合起來就有8種鏈表結(jié)構(gòu)：
1.單向或者雙向

2.帶頭或者不帶頭

3.循環(huán)或者非循環(huán)

雖然有這么多的鏈表的結(jié)構(gòu)，但是我們重點掌握兩種:
無頭單向非循環(huán)鏈表：結(jié)構(gòu)簡單，一般不會單獨用來存數(shù)據(jù)。實際中更多是作為其他數(shù)據(jù)結(jié)構(gòu)的子結(jié)構(gòu)，如哈希桶、圖的鄰接表等等。另外這種結(jié)構(gòu)在筆試面試中出現(xiàn)很多。

3.鏈表的實現(xiàn)

3.1 IList接口

public interface IList {
    //頭插法
    void addFirst(int data);
    //尾插法
    void addLast(int data);
    //任意位置插入,第一個數(shù)據(jù)節(jié)點為0號下標(biāo)
    void addIndex(int index,int data);
    //查找是否包含關(guān)鍵字key是否在單鏈表當(dāng)中
    boolean contains(int key);
    //刪除第一次出現(xiàn)關(guān)鍵字為key的節(jié)點
    void remove(int key);
    //刪除所有值為key的節(jié)點
    void removeAllKey(int key);
    //得到單鏈表的長度
    int size();
    void clear();
    void display();
}

3.2MyLinkList實現(xiàn)

public class MyLinkList implements IList{
    //內(nèi)部類
    class Node{
        public int val;
        public Node next;//下一個結(jié)點
        public Node head;//頭結(jié)點
        public Node(int val){
            this.val=val;
        }
    }  
    //自己創(chuàng)造的一個鏈表
    public void create(){
        Node node1=new Node(1);
        Node node2=new Node(2);
        Node node3=new Node(3);
        node1.next=node2;
        node2.next=node3;
       head= node1;
    }
    //頭插法
    @Override
    public void addFirst(int data) {
        Node node=new Node(data);
        node.next=head;
        head=node;
    }
    //尾插法
    @Override
    public void addLast(int data) {
    Node node=new Node(data);
    Node end=head;
    while (end.next!=null){
        end=end.next;
    }
    end.next=node;
    }
    //在某一個位置插入一個元素
    @Override
    public void addIndex(int index, int data) {
    if(index<0||index>size()){
        System.out.println("位置不合法");
        return;
    }
    if(index==0){
        addFirst(data);
        return;
    }
    if(index==size()){
        addLast(data);
        return;
    }
    Node node=new Node(data);
    Node pre=getNode(index);
    node.next=pre.next;
    pre.next=node;
    }
    public Node getNode(int index){
        Node node=head;
        while (index-1!=0){
            node=node.next;
            index--;
        }
        return node;
    }
	//是否包含某一個元素
    @Override
    public boolean contains(int key) {
        Node node=head;
        while (node!=null){
            if(node.val==key){
                return true;
            }
            node=node.next;
        }
        return false;
    }
	//刪除第一個為key的元素
    @Override
    public void remove(int key) {
    if(head.val==key){
        head=head.next;
        return;
    }
    int index=getindex(key);
    Node node=head;

    while (index-1!=0){
        node=node.next;
        index--;
    }
    node.next=node.next.next;
    }
    //根據(jù)key返回它的前一個坐標(biāo)
    public int getindex(int key){
        int count=0;
        Node node=head;
        while (node!=null){
            if(node.val==key){
                return count;
            }
            node=node.next;
            count++;
        }
        return -1;
    }
	//刪除所有為key的元素
    @Override
    public void removeAllKey(int key) {
    if (head==null){
        return;
    }
    Node node=head;
    Node cur=head.next;
    while (cur!=null){
        if(cur.val==key){
            node.next=cur.next;
            cur=cur.next;
        }else {
            node=node.next;
            cur=cur.next;
        }
    }
    if(head.val==key){
        head=head.next;
    }
    }
	//求鏈表大小
    @Override
    public int size() {
        Node node=head;
        int count=0;
        while (node!=null){
           count++;
            node=node.next;
        }
        return count;
    }
	//清空鏈表
    @Override
    public void clear() {
    Node node=head;
    while (node!=null){
        Node next=node.next;
        node.next=null;
        node=next;
    }
    head=null;
    }
	//打印鏈表
    @Override
    public void display() {
        Node node=head;
        while (node!=null){
            System.out.print(node.val+" ");
            node=node.next;
        }

    }
}

3.3 Test

public class Test {
    public static void main(String[] args) {
        MyLinkList myLinkList=new MyLinkList();
        myLinkList.create();
        myLinkList.display();
        System.out.println();
        //頭插法
        System.out.println("頭插法");
        myLinkList.addFirst(12);
        myLinkList.addFirst(13);
        myLinkList.addFirst(14);
        myLinkList.display();
        System.out.println();
        //尾插法
        System.out.println("尾插法");
        myLinkList.addLast(21);
        myLinkList.addLast(22);
        myLinkList.addLast(23);
        myLinkList.display();
        System.out.println();
        //中間位置插入
        System.out.println("在1位置插入100");
        myLinkList.addIndex(1,100);
        myLinkList.addIndex(1,100);
        myLinkList.addIndex(1,100);
        myLinkList.display();
        System.out.println();
        //查找元素
        Boolean a=myLinkList.contains(100);
        System.out.println(a);
        //刪除第一個100元素
        myLinkList.remove(100);
        myLinkList.display();
        System.out.println();
        //刪除所有100的元素
        myLinkList.removeAllKey(100);
        myLinkList.display();
        System.out.println();
        //求size
        int Size=myLinkList.size();
        System.out.println(Size);
        //清空鏈表
        myLinkList.clear();
        myLinkList.display();
    }
}

輸出結(jié)果如下：

4.LinkedList

LinkedList的底層是雙向鏈表結(jié)構(gòu)，由于鏈表沒有將元素存儲在連續(xù)的空間中，元素存儲在單獨的節(jié)點中，然后通過引用將節(jié)點連接起來了，因此在在任意位置插入或者刪除元素時，不需要搬移元素，效率比較高。
LinkedList源碼：

【說明】
通過上圖所示，我們可以知道LinkedList實現(xiàn)了List接口,LinkedList的底層使用了雙向鏈表。

4.1 LinkedList的使用

構(gòu)造：

 public static void main(String[] args) {
 // 構(gòu)造一個空的LinkedList
 List<Integer> list1 = new LinkedList<>();
 List<String> list2 = new java.util.ArrayList<>();
 list2.add("JavaSE");
 list2.add("JavaWeb");
 list2.add("JavaEE");
 // 使用ArrayList構(gòu)造LinkedList
 List<String> list3 = new LinkedList<>(list2);
 }

其他常用方法：

4.2 LinkedList的遍歷

LinkedList<Integer> 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());
    // foreach遍歷
    for (int e:list) {
        System.out.print(e + " ");
    }
    System.out.println();
    // 使用迭代器遍歷---正向遍歷
    ListIterator<Integer> it = list.listIterator();
    while(it.hasNext()){
        System.out.print(it.next()+ " ");
    }
    System.out.println()；

4.3ArrayList和LinkedList的區(qū)別

本篇文章主要介紹了鏈表的基礎(chǔ)知識，簡單介紹了什么是鏈表以及如何實現(xiàn)一個鏈表，以及LinkedList的操作方法，在下一篇文章中博主將帶領(lǐng)同學(xué)們一起學(xué)習(xí)鏈表的相關(guān)習(xí)題。

下期預(yù)告：鏈表經(jīng)典練習(xí)題文章來源地址http://www.zghlxwxcb.cn/news/detail-849465.html

到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)（三）】鏈表與LinkedList的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！