Java中的單向鏈表詳解

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

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

概述

單線鏈表：單向鏈表又叫單鏈表，是鏈表的一種。由節(jié)點構(gòu)成，head指針指向第一個稱為表頭節(jié)點,而終止指向最后一個null指針

特點

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

結(jié)構(gòu)

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

優(yōu)點

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

缺點

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

案例

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

public class Node {
    //存儲節(jié)點的值
    int val;
    //下一個節(jié)點地址
    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;
    }
}

測試

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

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

public class NodeTest {
    //實際存儲的個數(shù)，相當(dāng)于火車車廂的個數(shù)
    private int size;
    //第一個節(jié)點，相當(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é)點，要判斷當(dāng)前的鏈表是否為空,如果一個都沒有，那么就要插入第一個節(jié)點
        Node node = new Node(data);
        if (size == 0) {
            head = node;
            size++;
        } else {
            //當(dāng)前的火車已經(jīng)存在節(jié)點了
            // 頭部為上一個節(jié)點
            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ù)，相當(dāng)于火車車廂的個數(shù)
    private int size;
    //第一個節(jié)點，相當(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é)點，要判斷當(dāng)前的鏈表是否為空,如果一個都沒有，那么就要插入第一個節(jié)點
        Node node = new Node(data);
        if (size == 0) {
            head = node;
            size++;
        } else {
            //當(dāng)前的火車已經(jīng)存在節(jié)點了
            Node last = head;
            while (last.next != null) {
                last = last.next;
            }
            // 頭部為上一個節(jié)點
            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

圖片詳解

代碼實現(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;
        }
        //說明此時index合法，并且時在中間這個位置,此時需要知道index的前驅(qū)節(jié)點，單鏈表只能從前往后遍歷
        //將要插入的鏈表值添加進(jìn)去
        Node node = new Node(data);
        //獲取到整個鏈表值
        Node result = head;
        for (int i = 0; i < index - 1; i++) {
            //移除大于index-1的頭部數(shù)據(jù)
            result = result.next;
        }
        //將上面尾巴數(shù)據(jù)賦值過去，要注意這里時next，所以實際上是head的next，比如4 0 1 ，next的話是0 1
        //node的數(shù)據(jù)還是剛剛添加的數(shù)據(jù)，這個時候就會變成了data+result.next的數(shù)據(jù)
        node.next = result.next;
        //將result中的next對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é)點上的數(shù)據(jù)
    public int get(int index) {
        if (index < 0 || index >= size) {
            System.out.println("獲取鏈表位置index值失敗...");
            return -1;
        }
        //獲取到前一個節(jié)點
        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é)點1的數(shù)據(jù)" + test.get(1));
    }

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

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

//對下標(biāo)的某個值進(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、判斷鏈表是否包含某個值

輸出: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、移除鏈表中第一個值

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

//移除第一個值    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)移除對應(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é)點,del就是你要刪除的節(jié)點
            Node del = node.next;
            //將兩個節(jié)點給連接起來
            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、刪除指定元素的第一個節(jié)點

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

//刪除指定元素的第一個節(jié)點
    public void removeValueFirst(int data) {
        //先判斷頭節(jié)點情況,看看頭節(jié)點是不是正好等于待刪除節(jié)點
        if (head.val == data) {
            removeFirst();
        } else {
            //先找到待刪除的節(jié)點
            Node node = head;
            while (node.next != null) {
                //找到待刪除節(jié)點,找到了以后可以直接刪除
                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é)點

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

//刪除鏈表中包含值的所有節(jié)點
    public void removeValueAll(int data) {
        //判斷頭節(jié)點
        while (head != null && head.val == data) {
            removeFirst();
        }
        if (head == null) {
            System.out.println("當(dāng)前節(jié)點已經(jīng)為空了!");
            return;
        }
        //頭節(jié)點處理完畢，并且鏈表不等于空
        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)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: