数据结构之线性表（一）

定义

线性表：零个或者多个数据元素的有限序列，注意线性表的第一个元素没有前驱，最后一个元素没有后继，指向为空，并且任意一个元素仅仅对应一个或零个元素。

存储结构

顺序存储结构

顺序存储结构指的是用一段地址连续的存储单元依次存储线性表的元素，顺序存储结构具有三个特性：

存储空间的起始位置
线性表的最大存储量：定义线性表中最多能存储多少数据，在存储分配后一般是不变的
线性表当前长度：随着线性表元素的增加或减少，这个变量是变化的
线性表中每个元素占用的存储单元是固定的，所以知道了线性表中任意一个元素的地址就可以随时计算出其他元素的地址

线性表的元素查找时间复杂度为$O(1)$，而元素的插入和删除的复杂度都为$O(n)$，因为牵一发而动全身，每个数据的地址都会随着元素插入和删除而跟着改变，这也是它最大的缺点。

下面是Python文档中list操作的时间复杂度统计：

可以看出，在Python中，list的就是采用的顺序存储结构，从Python官方的文档说明list最大的开销来自于当前分配空间的变化，因为一旦插入或删除某个元素，其他所有的元素都必须得跟着移动。

Internally, a list is represented as an array; the largest costs come from growing beyond the current allocation size (because everything must move), or from inserting or deleting somewhere near the beginning (because everything after that must move). If you need to add/remove at both ends, consider using a collections.deque instead.

链式存储结构

链式存储结构区别于顺序存储结构的地方在于，它的数据元素除了存储数据元素信息，还需要存储后继元素的存储地址。另外，对于顺序存储结构，它在内存中的存储必须是连续的，而链式存储结构则不受此影响，内存中未被占用的任意位置都能被链式存储结构利用起来，所以它没有顺序存储结构遗留的“碎片”问题。

除了存储元素信息的数据域，还需要存储它后继元素的存储位置——指针域
头指针与头节点：头指针不能为空，它是链表必要元素；头结点不是必要元素，头节点的数据域可以不存储任何信息，也可以存储如线性表长度等类的附加信息，头结点的指针域存储指向第一个结点的指针（即第一个元素结点的存储位置）

线性表的 leetcode 题

Remove Nth Node From End of List

Medium

Given a linked list, remove the n-th node from the end of list and return its head.

Example:

1
2
3

Given linked list: 1->2->3->4->5, and n = 2.

After removing the second node from the end, the linked list becomes 1->2->3->5.

Note:

Given n will always be valid.

Follow up:

Could you do this in one pass?

给定一个线性表，要求删除从尾部开始数第n个节点，并返回，题目要求一次遍历就完成，解法：

这一题用到了快慢指针，快指针比慢指针快n步，所以当快指针到达链表的末尾时，慢指针刚好距离末尾还有n个距离。

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def removeNthFromEnd(self, head, n):
        """
        :type head: ListNode
        :type n: int
        :rtype: ListNode
        """
        dummy = ListNode(0)  # 初始化一个dummy
        dummy.next = head
        slow = fast = dummy
        
        for _ in range(n):  # 快指针先走n步
            fast = fast.next
            
        while fast.next:    # 当快指针到达链表的末尾，慢指针距离末尾n
            fast = fast.next
            slow = slow.next
            
        slow.next = slow.next.next  # 慢指针直接越过下一个Node
        return dummy.next

Reverse Linked List

Easy

Reverse a singly linked list.

Example:

1 2	Input: 1->2->3->4->5->NULL Output: 5->4->3->2->1->NULL

Follow up:

A linked list can be reversed either iteratively or recursively. Could you implement both?

这是一道翻转链表的题目，难度程度为easy。

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def reverseList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        prev = None  # 初始化一个为null的节点
        while head != None:
            tmp = head.next  # 将head.next临时存放在tmp中
            head.next = prev # head.next指向先前的null
            prev = head  # prev往后移动一个节点
            head = tmp   # head往后移动一个节点
        return prev