Java中的單向鏈表詳解

更新時(shí)間：2024年01月17日 10:37:33 作者：java-zh

這篇文章主要介紹了Java中的單向鏈表詳解,單向鏈表又叫單鏈表,是鏈表的一種,由節(jié)點(diǎn)構(gòu)成,head指針指向第一個(gè)稱為表頭節(jié)點(diǎn),而終止指向最后一個(gè)null指針,需要的朋友可以參考下

概述

單線鏈表：?jiǎn)蜗蜴湵碛纸袉捂湵恚擎湵淼囊环N。由節(jié)點(diǎn)構(gòu)成，head指針指向第一個(gè)稱為表頭節(jié)點(diǎn),而終止指向最后一個(gè)null指針

特點(diǎn)

鏈表連接的方向都是單向的
鏈表的訪問要通過順序從頭部開始
鏈表是使用指針進(jìn)行構(gòu)造的列表
是由一個(gè)一個(gè)節(jié)點(diǎn)組成的鏈表，又稱為節(jié)點(diǎn)鏈表
每個(gè)節(jié)點(diǎn)都有指針成員變量指向鏈表中的下個(gè)節(jié)點(diǎn)

結(jié)構(gòu)

可以比喻成火車，head是火車頭data是火車廂，每一個(gè)火車廂的車廂next都拉著一個(gè)下一個(gè)車廂

優(yōu)點(diǎn)

單個(gè)節(jié)點(diǎn)的創(chuàng)建非常方便(增)
節(jié)點(diǎn)的刪除非常方便，不需要線性結(jié)構(gòu)那樣移動(dòng)數(shù)據(jù)(刪)

缺點(diǎn)

只能沖頭到位遍歷，只能后續(xù)，無法找到前驅(qū)，也就是只能前進(jìn)
查詢時(shí)搜索遍歷需要遍歷整個(gè)鏈表，在不好的情況下，可能需要道鏈尾才能找到
鏈表需要維護(hù)next域，暫用內(nèi)存

案例

創(chuàng)建一個(gè)單向列表

public class Node {
    //存儲(chǔ)節(jié)點(diǎn)的值
    int val;
    //下一個(gè)節(jié)點(diǎn)地址
    Node next;
    public Node(int val) {
        this.val = val;
    }
    public Node(int val, com.study.data.linked.Node next) {
        this.val = val;
        this.next = next;
    }
}

測(cè)試

1、插頭法，從頭部上添加數(shù)據(jù)

輸出結(jié)果:5->4->3->3->2->NULL

public class NodeTest {
    //實(shí)際存儲(chǔ)的個(gè)數(shù)，相當(dāng)于火車車廂的個(gè)數(shù)
    private int size;
    //第一個(gè)節(jié)點(diǎn)，相當(dāng)于火車頭
    private Node head;
    /**
     * 用來展示鏈表
     *
     * @return
     */
    public String showNode() {
        StringBuilder ret = new StringBuilder();
        Node node = head;
        while (node != null) {
            ret.append(node.val).append("->");
            // 繼續(xù)訪問下一節(jié)車廂
            node = node.next;
        }
        ret.append("NULL");
        return ret.toString();
    }
    //在頭部上增加鏈數(shù)據(jù)(插頭罰)，如果鏈表為空，那么就是增加火車頭
    public void addFirst(int data) {
        //要向鏈表中添加節(jié)點(diǎn)，要判斷當(dāng)前的鏈表是否為空,如果一個(gè)都沒有，那么就要插入第一個(gè)節(jié)點(diǎn)
        Node node = new Node(data);
        if (size == 0) {
            head = node;
            size++;
        } else {
            //當(dāng)前的火車已經(jīng)存在節(jié)點(diǎn)了
            // 頭部為上一個(gè)節(jié)點(diǎn)
            node.next = head;
            head = node;
            size++;
        }
    }
    public static void main(String[] args) {
        NodeTest test = new NodeTest();
        test.addFirst(2);
        test.addFirst(3);
        test.addFirst(3);
        test.addFirst(4);
        test.addFirst(5);
        System.out.println(test.showNode());
    }
}

2、插尾法(從尾部開始插入數(shù)據(jù))

輸出結(jié)果:2->3->3->4->5->NULL

public class NodeTest {
    //實(shí)際存儲(chǔ)的個(gè)數(shù)，相當(dāng)于火車車廂的個(gè)數(shù)
    private int size;
    //第一個(gè)節(jié)點(diǎn)，相當(dāng)于火車頭
    private Node head;
    /**
     * 用來展示鏈表
     *
     * @return
     */
    public String showNode() {
        StringBuilder ret = new StringBuilder();
        Node node = head;
        while (node != null) {
            ret.append(node.val).append("->");
            // 繼續(xù)訪問下一節(jié)車廂
            node = node.next;
        }
        ret.append("NULL");
        return ret.toString();
    }
    //插尾法，從尾部開始添加數(shù)據(jù)
    public void addLast(int data) {
        //要向鏈表中添加節(jié)點(diǎn)，要判斷當(dāng)前的鏈表是否為空,如果一個(gè)都沒有，那么就要插入第一個(gè)節(jié)點(diǎn)
        Node node = new Node(data);
        if (size == 0) {
            head = node;
            size++;
        } else {
            //當(dāng)前的火車已經(jīng)存在節(jié)點(diǎn)了
            Node last = head;
            while (last.next != null) {
                last = last.next;
            }
            // 頭部為上一個(gè)節(jié)點(diǎn)
            last.next = node;
            size++;
        }
    }
    public static void main(String[] args) {
        NodeTest test = new NodeTest();
        test.addLast(2);
        test.addLast(3);
        test.addLast(3);
        test.addLast(4);
        test.addLast(5);
        System.out.println(test.showNode());
    }
}

3、在鏈表的中間插入位置

輸出結(jié)果:5->4->4->3->3->2->NULL

圖片詳解

代碼實(shí)現(xiàn)

 //在鏈表的中間插入位置
    public void addIndex(int index, int data) {
        //判斷邊界條件，判斷index的合法性
        if (index < 0 || index > size) {
            System.out.println("插入鏈表位置失敗....");
            return;
        }
        if (index == 0) {
            // 從鏈表的頭部開始插入
            addFirst(data);
            return;
        }
        //說明此時(shí)index合法，并且時(shí)在中間這個(gè)位置,此時(shí)需要知道index的前驅(qū)節(jié)點(diǎn)，單鏈表只能從前往后遍歷
        //將要插入的鏈表值添加進(jìn)去
        Node node = new Node(data);
        //獲取到整個(gè)鏈表值
        Node result = head;
        for (int i = 0; i < index - 1; i++) {
            //移除大于index-1的頭部數(shù)據(jù)
            result = result.next;
        }
        //將上面尾巴數(shù)據(jù)賦值過去，要注意這里時(shí)next，所以實(shí)際上是head的next，比如4 0 1 ，next的話是0 1
        //node的數(shù)據(jù)還是剛剛添加的數(shù)據(jù)，這個(gè)時(shí)候就會(huì)變成了data+result.next的數(shù)據(jù)
        node.next = result.next;
        //將result中的next對(duì)node進(jìn)行替換，上面的node已經(jīng)完成了拼接
        result.next = node;
        size++;
    }
    public static void main(String[] args) {
        NodeTest test = new NodeTest();
        test.addFirst(2);
        test.addFirst(3);
        test.addFirst(3);
        test.addFirst(4);
        test.addFirst(5);
        test.addIndex(2,4);
        System.out.println(test.showNode());
    }

4、獲取下標(biāo)中的數(shù)據(jù)

輸出結(jié)果:4

 // 查詢index節(jié)點(diǎn)上的數(shù)據(jù)
    public int get(int index) {
        if (index < 0 || index >= size) {
            System.out.println("獲取鏈表位置index值失敗...");
            return -1;
        }
        //獲取到前一個(gè)節(jié)點(diǎn)
        Node node = head;
        for (int i = 0; i < index; i++) {
            node = node.next;
        }
        return node.val;
    }
    public static void main(String[] args) {
        NodeTest test = new NodeTest();
        test.addFirst(2);
        test.addFirst(3);
        test.addFirst(3);
        test.addFirst(4);
        test.addFirst(5);
        System.out.println(test.showNode());
        System.out.println("獲取節(jié)點(diǎn)1的數(shù)據(jù)" + test.get(1));
    }

5、對(duì)鏈表中某個(gè)值進(jìn)行替換

輸出結(jié)果:5->4->0->3->2->NULL

//對(duì)下標(biāo)的某個(gè)值進(jìn)行替換
    public int set(int index, int data) {
        if (index < 0 || index >= size) {
            System.out.println("修改單鏈表中的數(shù)據(jù)失敗");
            return -1;
        }
        Node node = head;
        for (int i = 0; i < index; i++) {
            node = node.next;
        }
        //需要替換位置的值
        int oldData = node.val;
        // 進(jìn)行值替換
        node.val = data;
        return oldData;
    }
 
    public static void main(String[] args) {
        NodeTest test = new NodeTest();
        test.addFirst(2);
        test.addFirst(3);
        test.addFirst(3);
        test.addFirst(4);
        test.addFirst(5);
        test.set(2,0);
        System.out.println(test.showNode());
    }

6、判斷鏈表是否包含某個(gè)值

輸出:true

// 判斷鏈表中是否包含元素data
    public boolean contains(int data) {
        Node node = head;
        while (node != null) {
            if (node.val == data) {
                System.out.println("找到了元素" + data);
                return true;
            }
            node = node.next;
        }
        System.out.println("沒有找到元素" + data);
        return false;
    }
 
    public static void main(String[] args) {
        NodeTest test = new NodeTest();
        test.addFirst(2);
        test.addFirst(3);
        test.addFirst(3);
        test.addFirst(4);
        test.addFirst(5);
        System.out.println(test.contains(5));
        System.out.println(test.showNode());
    }

7、移除鏈表中第一個(gè)值

輸出結(jié)果:4->3->3->2->NULL

//移除第一個(gè)值    public void removeFirst() {        if (size == 0) {            return;        }        Node node = head;        head = node.next;        node.next = null;        size--;    }    public static void main(String[] args) {        NodeTest test = new NodeTest();        test.addFirst(2);        test.addFirst(3);        test.addFirst(3);        test.addFirst(4);        test.addFirst(5);        test.removeFirst();        System.out.println(test.showNode());    }

8、通過下標(biāo)移除對(duì)應(yīng)的值

輸出結(jié)果:5->4->3->2->NULL

//通過下標(biāo)移除值
    public void removeIndex(int index) {
        if (index < 0 || index > size) {
            System.out.println("通過下標(biāo)移除失敗,下標(biāo)異常");
        }
        if (index == 0) {
            removeFirst();
        } else {
            Node node = head;
            for (int i = 0; i < index - 1; i++) {
                node = head.next;
            }
            // node是待刪除的頭部節(jié)點(diǎn),del就是你要?jiǎng)h除的節(jié)點(diǎn)
            Node del = node.next;
            //將兩個(gè)節(jié)點(diǎn)給連接起來
            node.next = del.next;
            del.next = null;
            size--;
        }
    }
 
    public static void main(String[] args) {
        NodeTest test = new NodeTest();
        test.addFirst(2);
        test.addFirst(3);
        test.addFirst(3);
        test.addFirst(4);
        test.addFirst(5);
        test.removeIndex(2);
        System.out.println(test.showNode());
    }

9、刪除指定元素的第一個(gè)節(jié)點(diǎn)

輸出:5->4->3->2->NULL

//刪除指定元素的第一個(gè)節(jié)點(diǎn)
    public void removeValueFirst(int data) {
        //先判斷頭節(jié)點(diǎn)情況,看看頭節(jié)點(diǎn)是不是正好等于待刪除節(jié)點(diǎn)
        if (head.val == data) {
            removeFirst();
        } else {
            //先找到待刪除的節(jié)點(diǎn)
            Node node = head;
            while (node.next != null) {
                //找到待刪除節(jié)點(diǎn),找到了以后可以直接刪除
                if (node.next.val == data) {
                    Node del = node.next;
                    node.next = del.next;
                    del.next = null;
                    size--;
                    break;
                } else {
                    node = node.next;
                }
            }
        }
    }
 
    public static void main(String[] args) {
        NodeTest test = new NodeTest();
        test.addFirst(2);
        test.addFirst(3);
        test.addFirst(3);
        test.addFirst(4);
        test.addFirst(5);
        test.removeValueFirst(3);
        System.out.println(test.showNode());
    }

10、刪除鏈表中的所有節(jié)點(diǎn)

輸出結(jié)果:5->4->2->NULL

//刪除鏈表中包含值的所有節(jié)點(diǎn)
    public void removeValueAll(int data) {
        //判斷頭節(jié)點(diǎn)
        while (head != null && head.val == data) {
            removeFirst();
        }
        if (head == null) {
            System.out.println("當(dāng)前節(jié)點(diǎn)已經(jīng)為空了!");
            return;
        }
        //頭節(jié)點(diǎn)處理完畢，并且鏈表不等于空
        Node node = head;
        while (node.next != null) {
            //12345
            if (node.next.val == data) {
                Node del = node.next;
                node.next = del.next;
                del.next = null;
                size--;
 
            } else {
                node = node.next;
            }
        }
 
    }
 
    public static void main(String[] args) {
        NodeTest test = new NodeTest();
        test.addFirst(2);
        test.addFirst(3);
        test.addFirst(3);
        test.addFirst(4);
        test.addFirst(5);
        test.removeValueAll(3);
        System.out.println(test.showNode());
    }

到此這篇關(guān)于Java中的單向鏈表詳解的文章就介紹到這了,更多相關(guān)Java單向鏈表內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: