线性表长度和链表长度

在线性表中，其长度通常指的是元素的数量，包括空表（长度为0）和非空表。对于数组表示的线性表，长度可以通过计算数组的大小来得到，因为数组有一个固定的大小，即元素的个数。例如，在Python中，可以这样获取数组的长度[^2]：

# 假设array是一个列表
length = len(array)

而对于链表，特别是非顺序存储的链表（如单向链表或双向链表），长度通常是通过遍历节点并计数来确定的，因为它没有预先定义的固定大小。在双向链表中，由于每个节点有两个指针，一个指向前面的节点，另一个指向后面的节点，所以计算长度的过程可能涉及到更多的操作[^1]。

class Node:
    def __init__(self, data=None):
        self.data = data
        self.prev = None
        self.next = None

def get_dbl_linked_list_length(head):
    current = head
    count = 0
    while current is not None:
        count += 1
        current = current.next
    return count

在这个示例中，`get_dbl_linked_list_length`函数会返回双向链表的长度。

相关问题

线性表和链表区别链表有啥优势

线性表是数据结构中的一种基本形式，它是n个数据元素的有限序列。线性表具有以下特点：元素之间有序，除第一个和最后一个元素外，每个元素都有一个直接前驱和一个直接后继。

链表是一种常见的数据结构，它由一系列节点组成，每个节点都包含一个数据元素和一个指向下一个节点的指针。链表具有以下特点：不要求在内存中连续存储，可以动态添加和删除节点，可以灵活地调整链表的长度。

链表相比线性表有以下优势：
1. 插入和删除操作更高效：由于链表的特性，插入和删除一个节点只需要修改指针的指向，不需要移动其他节点，因此操作效率更高。
2. 动态扩展：链表的长度可以根据需要进行动态扩展，而线性表的长度是固定的。
3. 空间利用率高：链表只在需要时分配内存，不会造成内存的浪费。

己知长度未知的线性表L采用链表结构。设计 一个时间复杂度为O(n)空间复杂度为O(1）的算法，该算 法实现单链表逆置

思路：

1. 定义三个指针：pre、cur、next，分别指向当前节点的前一个节点、当前节点和当前节点的后一个节点。

2. 遍历链表，将当前节点的 next 指针指向前一个节点，更新三个指针的位置，继续遍历。

3. 遍历完成后，将原链表的头节点指向逆置后的链表的头节点即可。

代码实现：

void reverseList(ListNode* &head) {
    ListNode* pre = nullptr;
    ListNode* cur = head;
    ListNode* next = nullptr;
    while (cur != nullptr) {
        next = cur->next;
        cur->next = pre;
        pre = cur;
        cur = next;
    }
    head = pre;
}

时间复杂度为O(n)，空间复杂度为O(1)。