java單鏈表使用總結

Posted on by

鏈表的概念:

鏈表是一種物理存儲單元上非連續、非順序的存儲結構，數據元素的邏輯順序是通過鏈表中的指針鏈接次序實現的。鏈表由一系列節點(鏈表中的每一個元素稱為節點)組成，節點可以在運行時動態生成。每個節點包含兩個部分:一個是存儲數據元素的數據域，另一個是存儲下一個節點地址的指針域。相對於線性表順序結構，操作復雜。由於不必按順序存儲，鏈表在插入的時候可以達到O(1)的復雜度，比另一種線性表順序表快得多，但查找一個節點或者訪問特定編號的節點則需要O(n)的時間，而線性表和順序表相應的時間復雜度分別是O(logn)和O(1)。

鏈表的優勢

不需要知道數據的大小，可以充分利用計算機內存空間，實現靈活的內存動態管理
鏈表允許插入和移除表上任意位置上的節點(但是不允許隨機存取)

鏈表的缺點

不能像數組一樣隨機讀取
增加瞭空間的開銷(增加瞭節點的指針域)

代碼實現

定義一個節點類

public class ListNode {//定義節點類
    int val;
    ListNode next;
 
    ListNode(int x) {
        val = x;
    }
 
    //將數組的值賦給鏈表
    public ListNode getList(int[] sums) {
        ListNode dummyHead = new ListNode(0);
        ListNode curr = dummyHead;
        for (int i = 0; i < sums.length; i++) {
            curr.next = new ListNode(sums[i]);
            curr = curr.next;
        }
        return dummyHead.next;
    }
 
    //將鏈表的值賦給list並打印
    public void showList(ListNode listNode) {
        List list = new ArrayList();
        while (listNode != null) {
            list.add(listNode.val);
            listNode = listNode.next;
        }
        for (int i = 0; i < list.size(); i++) {
            System.out.println(list.get(i));
        }
    }
 
    /**
     * leetcode第二題
     *
     * 給出兩個非空的鏈表用來表示兩個非負的整數，
     * 其中，它們各自的位數是按照逆序的方式存儲的，
     * 並且它們的每一個節點隻能存儲一位數組。
     * @param l1
     * @param l2
     * @return
     */
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dummyHead = new ListNode(0);
        ListNode p = l1, q = l2, curr = dummyHead;
        int carry = 0;
        while (p != null || q != null) {
            int x = (p != null) ? p.val : 0;
            int y = (q != null) ? q.val : 0;
            int sum = carry + x + y;
            carry = sum / 10;
            curr.next = new ListNode(sum % 10);
            curr = curr.next;
            if (p != null) p = p.next;
            if (q != null) q = q.next;
        }
        if (carry > 0) {
            curr.next = new ListNode(carry);
        }
        return dummyHead.next;
    }
}

測試方法

public class main {
    public static void main(String[] args) {
        int a[] = {2, 4, 3};
        int b[] = {5, 6, 4};
        ListNode curr=new ListNode(0);
        ListNode l1=curr.getList(a);
//        curr.showList(l1);
        ListNode l2=curr.getList(b);
//        curr.showList(l2);
        ListNode l3=curr.addTwoNumbers(l1,l2);
        curr.showList(l3);
    }
 
 
}

輸入[2,4,3],[5,6,4]

輸出[7,0,8]

以上就是本文的全部內容，希望對大傢的學習有所幫助，也希望大傢多多支持WalkonNet。

推薦閱讀：