算法和数据结构1.2链表

链表

链表是数据结构之一，其中的数据呈线性排列。在链表中，数据的添加和删除都很方便，就是访问的时候比较消耗时间。

链表操作

在链表中，数据一般都是分散存储于内存中的，无需存贮在连续的空间内。
链表中的每个节点可以理解为由一个数据区域和一个指针区域组合而成，数据区域用来存储数据，而指针区域用来存储下一个节点的地址。
所以在访问链表的数据时候，必须从第一个数据开始，顺着指针指向一一往下访问。

链表的添加数据：只需要改变添加位置前后的指针指向就可以了，非常简单~~

链表的删除数据：只要改变指针的指向就可以了，虽然看似在内存空间中没有清空被删除节点的数据。

但是无论从哪里都无法访问到这里的数据了，所以就没有特意去删除的必要了，而且如果未来需要用到这一块的内存区域，只需要新的数据覆盖掉就可以了。

链表操作时间预估

对链表的操作所需要的运行时间：假设链表中的数据节点量是n.访问数据时候，我们需要从链表头部开始查找（线性查找），如果目标数据在链表的最后的话，需要的时间就是O(n)

另外，添加数据只需要更改两个指针的指向，所以耗费的时间和n无关。

如果已经到达了添加数据的位置，那么添加操作只需花费O（1）的时间。删除数据也同样只需O(1)的时间。

非基本链表

以上提到的情况是最基本的一种链表。除此之外还存在几种扩展方便的链表。

假设将链表尾部的指针区域的值指向链表的头部的地址，这样就像是把链表首尾链接成了一个环形了。这便是循环链表，也叫做环形链表。

在实际概念中循环链表不具备头和尾的概念，而在实际应用中，想要保存数量固定的最新数据时候通常会用到这种链表。

另外，基本链表只有一个指针，但是我们可以把指针设定为两个，并且仍他们分别指向前后的数据节点，这种链表叫做双向链表。

双向链表不但可以从前往后遍历数据，还可以从后往前遍历数据。

双向链表存在两个缺点：

1.指针数量的增加会导致存储空间需求增加
2.添加和删除数据时候，需要改变更多指针的指向

链表的简单应用leetcode

给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。

如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。

您可以假设除了数字 0 之外，这两个数都不会以 0 开头。

示例：

输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807

package com.company;

public class Main {

    public static void main(String[] args) {
            ListNode l1 = new ListNode(2);
            ListNode l2 = new ListNode(5);
            l1.next = new ListNode(4);
            l2.next = new ListNode(6);
            l1.next.next = new ListNode(3);
            l2.next.next = new ListNode(4);
           System.out.println(ListNode.print(addTwonums(l1,l2)));
    }

    public static ListNode addTwonums(ListNode list1 , ListNode list2){
        if (list1 == null && list2 == null) {
            return null;
        }
        ListNode dummy = new ListNode(0);
        ListNode head = dummy;
        int addOne = 0;
        while (list1 != null || list2 != null || addOne != 0) {
            int v1 = (list1 != null) ? list1.val : 0;
            int v2 = (list2 != null) ? list2.val : 0;
            int sum = v1 + v2 + addOne;
            head.next = new ListNode(sum % 10);
            head = head.next;
            addOne = sum / 10;
          if (list1 != null) { list1 = list1.next;}
          if (list2 != null) {list2 = list2.next;}
        }

         return dummy.next;
    }

    public static class ListNode {
        int val;
        ListNode next;
        public ListNode(int val){
            this.val = val;
        }
        public static String print(ListNode l){
            StringBuilder sb = new StringBuilder();
            while (l != null){
                sb.append(l.val);
                l = l.next;
            }
            return sb.toString();
        }
    }

}