chapter_array_and_linkedlist/list/

[giscus[bot]]

chapter_array_and_linkedlist/list/

Your first book to learn Data Structure And Algorithm.

https://www.hello-algo.com/chapter_array_and_linkedlist/list/

[qualifier1024]

仿照大佬Java写了个c++本地运行没啥问题，不会上传

[krahets]

谢谢你的代码！可否请你根据 一起参与创作 中的教程步骤来提交代码？还是蛮简单的～ Git 工具比较常用，花一些时间学习的话还是很值得哒

[Blackcat308]

介绍数组缺点一项，在数组中插入或删除元素效率低下课题下，丢失元素或是否是语病？

[krahets]

谢谢您的指正，将改为 丢失元素： 由于数组的长度不可变，因此在插入元素后，超出数组长度范围的元素会被丢失。
（对于笔误，您也可以直接点击页面右上角的 铅笔 图标直接修改，谢谢哇～）

[mao888]

线性表的顺序存储，就是您这章所讲的列表吗？

[krahets]

哈喽，本章中的数组和列表，都属于线性表的顺序存储

[yuelinxin]

在列表末尾添加元素是不是也不严格为O(1)，比如某些情况下列表正好需要先扩容再添加，这时候时间复杂度就会是O(N)。请问Python中的list是否也会存在这种问题？

[krahets]

是的，遇到需要扩容时，系统会申请一块新的内存，并将原列表的所有元素搬运过去，此时会很慢。Python 也一样，应该没有语言能避开这个问题。

[ZZhenF]

如果创建多线程，并发的情况下，对同一个List操作，它怎么判断size的执行顺序

[yuelinxin]

多线程操作同一块内存应该是需要线程锁的，为了避免线程冲突，正常情况下所有对这个list的增删查改操作都需要在当前线程获取到了对这个list的控制权的情况下进行，因为size函数是对list的一个读取操作，所以执行size函数的顺序应该就是取决于哪个线程先获取到控制权，就先执行哪个线程中的size，也就是first come first serve（先到先得）了。

[zjy-coder]

这里只牵扯算法。多线程就别说了...

[is-liu]

如果需要线程安全的话在Java中是可以通过集合类包装一下
List<Integer> list = new ArrayList<>(Arrays.asList(1,2,3,4,5));
这样下面的就是一个线程安全的列表，至于其他语言就不大清楚了
List<Integer> syncList = Collections.synchronizedList(list);

[Gonglja]

cpp 中，vector 成员函数 size 的返回值类型为 size_type
在实际实践中，大多数 size_type 被转为 unsigned type，std::size_t unsigned int 或者 std::size_t unsigned long，祥见c-vector-size-types

vector<int> list = { 1, 3, 2, 5, 4 };
...
int count = 0;
- for (int i = 0; i < list.size(); i++) {
+ for (size_t i = 0; i < list.size(); i++) 
    count++;
}

[Gonglja]

还有其它地方使用 vector、unordered_map 的地方，类型都是 size_type，
vector size
unordered_map size

size_type 通常被定义为 std::size_t

[krahets]

确实，不过用 int 问题也不大，做题时比较方便

[PhiFever]

在最后的my_list.cpp中的 void extendCapacity() 方法似乎没有考虑整型溢出的风险（int newCapacity = capacity() * extendRatio;），由于extendRatio和numsCapacity都是int型，我认为这个风险还是蛮大的。或者说在这部分针对初学者的内容中暂时不用考虑这么细致？

[krahets]

确实！由于是简易实现，考虑到简洁性，没有考虑到那么细致～暂且假定本实现中列表最长仅支持 int 最大值。

[Teamsaa]

大佬，C语言版本的动态数组没有嘛，我记得C primer plus 有讲

[krahets]

Hi 抱歉暂时没有 C 代码，仍在开发中

[pasionfru]

大佬牛逼，这对新手很友好

[ThreeAurora]

这行太棒了，直接补充了我几个知识点~
List list1 = new ArrayList<>(Arrays.asList(new Integer[] { 6, 8, 7, 10, 9 }));

[ThreeAurora]

我打错了，是
List<Integer> list1 = new ArrayList<>(Arrays.asList(new Integer[] { 6, 8, 7, 10, 9 }));
这行好像可以移除显示数组创建
List<Integer> list1 = new ArrayList<>(Arrays.asList(6, 8, 7, 10, 9));

[highlineee]

写得好好啊！看了一堆课都不如大佬清清爽爽的梳理，但知识点又很全面了~新手老手都友好！

[lavamooncake-816]

不好意思我想请问一下，在列表类实现中，“# 新建一个长度为 self.__size 的数组，并将原数组拷贝到新数组”是否应该为“新建一个长度为 self.__nums 的数组“？

[krahets]

不是的，新数组的长度是 self.capacity() * (self.__extend_ratio - 1) ，为原数组的 self.__extend_ratio 倍

[jiangyigithub]

/* 列表扩容 */
void extendCapacity() {
    // 新建一个长度为原数组 extendRatio 倍的新数组
    int newCapacity = capacity() * extendRatio;
    int *tmp = nums;
    nums = new int[newCapacity];
    // 将原数组中的所有元素复制到新数组
    for (int i = 0; i < size(); i++) {
        nums[i] = tmp[i];
    }
    // 释放内存
    delete[] tmp;
    numsCapacity = newCapacity;
}

could you give me some explanation about the "new" and "delete[]" operator? why we double "new" int[] for nums,why need delete[] tmp?

the below is comment by CHATGPT:
"
However, there is a potential issue with this code. Since tmp is assigned the address of the original nums array, deleting tmp will free the memory associated with that array. But after that, nums will still point to the new array, leaving the original nums array undeleted and causing a memory leak.

To fix this, you can simply remove the line delete[] tmp;, as it is unnecessary and could lead to issues if you intend to continue using the nums array.
"

[krahets]

The delete[] tmp is for releasing the memory of the original array. The overall process is as follows:

1. Creating a new array with a bigger capacity.
2. Move the elements from the original array to the new array.
3. Release the memory of the original array to avoid memory leaks.

[yzWHS]

/* 中间插入元素 */
    void insert(int index, int num) {
        if (index < 0 || index >= size())
            throw out_of_range("索引越界");
        // 元素数量超出容量时，触发扩容机制
        if (size() == capacity())
            extendCapacity();
        // 索引 i 以及之后的元素都向后移动一位
        for (int j = size() - 1; j >= index; j--) {
            nums[j + 1] = nums[j];
        }
        nums[index] = num;
        // 更新元素数量
        numsSize++;
    }

里面的注释，索引i应该是j。

[krahets]

这里不是 j 哈，原文的 i 指的是 index

[qualifier1314]

看评论就学到了很多

[GuanmingBao]

vector nums = { 1, 3, 2, 5, 4 };
C++还可以这样初始化吗？

[xiaos2021]

https://blog.csdn.net/qq_33944628/article/details/134425676

[Kruogu]

链接我看过了，就没见过这种写法啊，vector vec(size());

[xiaos2021]

此处的 size() 是当前的自定义类 class MyList 的成员函数，跟 std::vector 没关系。

std::vector<Elem> c(n); // 调用元素的默认构造函数生成一个大小为n的vector， 如果Elem 是基础类型，那么每个元素会初始化为随机值，如果是对象，那么调用默认构造函数

[Kruogu]

也就是出定义vector容器内可以调用成员函数？

[NorthZeroD]

https://www.runoob.com/cplusplus/cpp-vector.html

[TanZiDong]

请问列表实现中的构造函数newMyList里，malloc前面为什么不用强转类型？

[PlusPEI]

在 C 语言中，malloc 函数的返回类型是 void *，它是一个通用指针类型，可以指向任何类型的数据。由于 void * 可以隐式转换为任何类型的指针，因此你可以直接将其赋值给一个特定类型的指针，而不需要强制类型转换。

在你的代码中，MyList *nums = malloc(sizeof(MyList)); 这行代码，malloc 返回的是 void * 类型，它会被自动转换为 MyList * 类型，因为 nums 已经声明为 MyList * 类型。C 编译器允许这种隐式类型转换，因此在 malloc 语句中不需要强制转换类型。

在 C++ 中，malloc 返回的是 void *，但为了类型安全，通常需要强制类型转换。但是在 C 语言中，这种强制类型转换是可选的，实际上也不推荐使用强制类型转换来处理 malloc 返回值，因为这可能会引入不必要的冗余代码。

总结：在 C 中，malloc 返回 void * 类型，可以直接赋值给任何类型的指针，因此不需要强制类型转换。

[PasserbyLin]

请问列表实现的c++代码那里，最后为什么是将列表转换为 Vector 用于打印 ，而不是和其他语言一样转换为数组打印？

[krahets]

hi 转换为数组或者 vector 都行的～

[Gyj918]

TS实现List中
public toArray(): Array {
let size = this._size;
const arr = new Array(size);
for (let i = 0; i < size; i++) {
arr[i] = this.arr[i];
}
return arr;
}
写成这样会不会更好
public toArray(): Array {
return this.arr.slice(0, this._size);
}

[xbsheng]

可能作者的目的是介绍具体的实现流程及原理，尽可能的避免一些语言特有的差异化语法，使用最基础的能力，方便各种语言基础的同学学习吧

[zoeyleeeee]

十分感谢！！想请教一个小问题，本节中对于拼接列表的介绍使用了加号运算符，这种方式的时间复杂度可否简单介绍一下，是平方阶吗，谢谢：）

[Lpf-357]

我觉得是1？他不是说”链表天然可以看作一个列表，其支持元素增删查改操作，并且可以灵活动态扩容”吗，只是增加了一个指针

[jiuerya7]

是O（n），列表的内部实现是数组，拼接其实是把新数组的元素添加到列表，无论是否触发扩容操作，都要循环遍历添加元素，只不过扩容的时候，多遍历了一次

[Cocopie-ye]

请教大家，在java语境下，判断插入元素时列表扩容条件为：
if (size == capacity())；
size和capacity都是Class MyList中的private instance variable，为什么size可以直接用，capacity要调用一个instance method呢？

[Durantttttttttttttt]

你也可以直接使用size == capacity啊，实例方法只是提供了一个类似get的操作

[Limit1996]

C#

namespace _1.Console;

public class CustomList<T>
{
    private T[] _array;
    private readonly int _capacity = 10;
    private int _count;
    public int Count => _count;

    public T this[int index]
    {
        get
        {
            VerifyIndex(index);
            return _array[index];
        }
        set
        {
            VerifyIndex(index);
            _array[index] = value;
        }
    }

    

    public CustomList() => _array = new T[_capacity];

    public void Add(T item)
    {
        EnsureCapacity();
        _array[_count++] = item;
    }

    public void Insert(int index, T item)
    {
        VerifyIndex(index);
        EnsureCapacity();
        for (int i = _count - 1; i >= index; i--)
            _array[i + 1] = _array[i];
        _array[index] = item;
        _count++;
    }

    public T RemoveAt(int index)
    {
        VerifyIndex(index);
        var element = _array[index];

        for (int i = index; i < _count; i++)
        {
            _array[i] = _array[i + 1];
        }

        _array[_count] = default!;
        _count--;
        return element;
    }

    public int FindIndex(T value)
    {
        if (value == null)
            return -1;

        for (int i = 0; i < _count; i++)
        {
            if (_array[i] == null)
                continue;
            if (_array[i]!.Equals(value))
                return i;
        }
        return -1;
    }

    private void EnsureCapacity()
    {
        if (_count >= _array.Length)
            Array.Resize(ref _array, _array.Length + _capacity);
    }
    
    private void VerifyIndex(int index)
    {
        if (index < 0 || index >= _count)
            throw new IndexOutOfRangeException("索引超出数组范围");
    }
}

[Canne11ia]

朱斌のおとうさん于2025.7.21留下书签,明日再看

[superZchen0701]

原来js中的数组是列表而不是数组。

[zouyonghe]

Rust也许用reserve扩容会好一些？

let new_capacity = self.capacity * self.extend_ratio;
self.arr.reserve(new_capacity - self.arr.capacity());
// 这里不改变 len()，只是提前申请内存
self.capacity = new_capacity;

[Canne11ia]

2025.7.13 18:50

朱斌のおとうさん关于列表在c++中的实现

#include <iostream>
#include <vector>

class MyList {
    private:
    int *arr;
    int arrCapacity = 10;
    int arrLength = 0;
    int extendRatio = 2;

    public:
    //Constructor
    MyList() : arr(new int[arrCapacity]) {}

    //Deconstructor
    ~MyList() {
        delete[] arr;
    }

    //Lenth of Array
    int length() {
        return arrLength;
    }

    //Capacity of Array
    int capacity() {
        return arrCapacity;
    }

    //Accessing Elements
    int get(int index) {
        if(index < 0 || index >= length()) {
            throw std::out_of_range("index out of range!");
        }
        return arr[index];
    }

    //Updating Elements
    void set(int index, int num) {
        if(index < 0 || index >= length()) {
            throw std::out_of_range("index out of range!");
        }
        arr[index] = num;
    }

    //Adding Elements at the End;
    void add(int num) {
        //When the number of elements exceeds capacity, trigger extending mechanism
        if(length() == capacity()) {
            extendCapacity();
        }
        arr[length()] = num;
        arrLength++;
    }

    //Inserting Elements
    void insert(int index, int num) {
        if(index < 0 || index >= length()) {
            throw std::out_of_range("index out of range!");
        }
        //When the number of elements exceeds capacity, trigger extending mechanism
        if(length() == capacity()) {
            extendCapacity();
        }
        //Moving the Elements
        for(int j = length() - 1; j >= index; j--) {
            arr[j + 1] = arr[j];
        }
        arr[index] = num;
        arrLength++;
    }

    //Deleting Elements
    int remove(int index) {
        if(index < 0 || index >= length()) {
            throw std::out_of_range("index out of range!");
        }
        int num = arr[index];
        //Moving Elements
        for(int j = index; j < length() - 1; j++) {
            arr[j] = arr[j + 1];
        }
        arrLength--;
        return num;
    }

    //Extending the List
    void extendCapacity() {
        //Initializing the Capacity of the Extended List
        int newCapacity = capacity() * extendRatio;
        int *tmp = arr;
        arr = new int[newCapacity];
        //Copying Elements to the New List
        for(int i = 0; i < length(); i++) {
            arr[i] = tmp[i];
        }
        //Releasing Memory
        delete[] tmp;
        arrCapacity = newCapacity;
    }

    //Convert to Vector
    std::vector<int> toVector() {
        //Only Convert the Elements within the Effective Range
        std::vector<int> vec(length());
        for(int i = 0; i < length(); i++) {
            vec[i] = arr[i];
        }
        return vec;
    }
};

[carteralexand]

二元的列表怎么实现呢

[carteralexand]

说错了 二维列表

[whplalala]

嵌套列表就行

[zhengads]

某种意义上来说，列表和数组是等价的

[limo06-sketch]

有没有链表版

[JiaXianS]

链表就和上一节的代码类似，这节主要是对每一个语言原有列表功能的二次封装。链表还不用管下标越界和扩容问题，就是基本的增删改查。
我上节写的代码如下：
"""链表操作， 使用类实例作为节点"""

class ListNode:
"""链表节点类， 一个属性存储值，一个属性指向下一个节点"""
def init(self, val: int):
# 链表节点类的构造函数， 需要传递一个参数
self.val: int = val
self.next: ListNode | None = None

def cread(nums: list[int]) -> ListNode | None:
"""根据数组创建链表，返回链表头节点"""
if not nums:
# 如果传入的数组为空，则返回None
return None

创建头节点

head: ListNode = ListNode(nums[0])
current_node: ListNode = head

循环创建节点

for i in range(1, len(nums)):
current_node.next = ListNode(nums[i])
# 让当前节点指向刚刚添加的节点
current_node = current_node.next

处理尾节点

current_node.next = None

return head

def traverse(listNode: ListNode):
"""遍历输出节点数据"""
current_node: ListNode = listNode

遍历链表输出每一个节点的值，最后一个节点为None会判断为False

while current_node:
print(current_node.val, end=" -> ")
current_node = current_node.next

print()

def insert(n0: ListNode, p: ListNode):
"""在链表中插入节点，需要给出要插入位置的节点对象n0， 并插入节点P"""
p.next = n0.next
n0.next = p

def remove(n0: ListNode):
"""在链表中删除节点n0之后的首个节点, 删除后的节点任然指向链表但是链表以及无法访问到该节点了，相当与删除了该节点，会被回收"""
p: ListNode = n0.next
n0.next = p.next
p = None

def find(listNode: ListNode, val: int) -> ListNode | None:
"""根据节点的值查找节点并返回，链表中没有该值则返回None"""
current_node: ListNode = listNode

遍历链表输出每一个节点的值，最后一个节点为None会判断为False

while current_node:
if current_node.val == val:
# 如果找到一个节点的值和给出的值相同则返回该节点
return current_node
current_node = current_node.next

没找到返回None

return None

def access(listNode: ListNode, index: int) -> ListNode | None:
"""根据节点的索引查找节点并返回，链表中没有该值则返回None"""
current_node: ListNode = listNode #虽然直接使用listNode局部变量也可以但是不方便区分

for _ in range(index):
# 索引只是表示为第几个节点不起实质性的作用,和数组的索引类似
if not current_node:
# 如果传入的节点为None的直接返回None退出
return None
current_node = current_node.next

return current_node

if name == "main":
listNode: ListNode = cread([1, 3, 2, 5, 4])
result: ListNode | None = None
traverse(listNode=listNode)
#############################################
result = find(listNode=listNode, val=4)

print(f"找到了！该节点为：{result}") if result else print(f"没找到！结果为{result}")
#############################################
result = access(listNode=listNode, index=0)
print(f"找到了！该节点为：{result.val}") if result else print(f"没找到！结果为{result}")

[JiaXianS]

"""链表操作， 使用类实例作为节点"""

class ListNode:
  """链表节点类， 一个属性存储值，一个属性指向下一个节点"""
  def __init__(self, val: int):
    # 链表节点类的构造函数， 需要传递一个参数
    self.val: int = val
    self.next: ListNode | None = None

def cread(nums: list[int]) -> ListNode | None:
  """根据数组创建链表，返回链表头节点"""
  if not nums:
    # 如果传入的数组为空，则返回None
    return None
  
  # 创建头节点
  head: ListNode = ListNode(nums[0])
  current_node: ListNode = head

  # 循环创建节点
  for i in range(1, len(nums)):
    current_node.next = ListNode(nums[i])
    # 让当前节点指向刚刚添加的节点
    current_node = current_node.next

  # 处理尾节点
  current_node.next = None

  return head

def traverse(listNode: ListNode):
  """遍历输出节点数据"""
  current_node: ListNode = listNode

  # 遍历链表输出每一个节点的值，最后一个节点为None会判断为False
  while current_node:
    print(current_node.val, end=" -> ")
    current_node = current_node.next

  print()

def insert(n0: ListNode, p: ListNode):
  """在链表中插入节点，需要给出要插入位置的节点对象n0， 并插入节点P"""
  p.next = n0.next
  n0.next = p

def remove(n0: ListNode):
  """在链表中删除节点n0之后的首个节点, 删除后的节点任然指向链表但是链表以及无法访问到该节点了，相当与删除了该节点，会被回收"""
  p: ListNode = n0.next
  n0.next = p.next
  p = None

def find(listNode: ListNode, val: int) -> ListNode | None:
  """根据节点的值查找节点并返回，链表中没有该值则返回None"""
  current_node: ListNode = listNode

  # 遍历链表输出每一个节点的值，最后一个节点为None会判断为False
  while current_node:
    if current_node.val == val:
      # 如果找到一个节点的值和给出的值相同则返回该节点
      return current_node
    current_node = current_node.next
  
  # 没找到返回None
  return None

def access(listNode: ListNode, index: int) -> ListNode | None:
  """根据节点的索引查找节点并返回，链表中没有该值则返回None"""
  current_node: ListNode = listNode     #虽然直接使用listNode局部变量也可以但是不方便区分

  for _ in range(index):
    # 索引只是表示为第几个节点不起实质性的作用,和数组的索引类似
    if not current_node:
      # 如果传入的节点为None的直接返回None退出
      return None
    current_node = current_node.next
  
  return current_node


if __name__ == "__main__":
  listNode: ListNode = cread([1, 3, 2, 5, 4])
  result: ListNode | None = None
  traverse(listNode=listNode)
  #############################################
  result = find(listNode=listNode, val=4)

  print(f"找到了！该节点为：{result}") if result else print(f"没找到！结果为{result}")
  #############################################
  result = access(listNode=listNode, index=0)
  print(f"找到了！该节点为：{result.val}") if result else print(f"没找到！结果为{result}")

[limo06-sketch]

让我来试试

[limo06-sketch]

加油

[limo06-sketch]

马上就好

[limo06-sketch]

高能代码：链表版列表-简化版
// Simplified version_My linked list version queue.cpp : This file contains the 'main' function. Program execution begins and ends there.
// this is a simplified version of a linked list implementation of a queue in C++.
// It includes basic operations such as adding an element to the back, removing an element from the front,
// retrieving the front element, clearing the queue, printing the queue, checking the size, and checking if it's empty.
#include
#include
#include
using namespace std;
struct LinkNode
{
friend class LinkedList;
private:
LinkNode* next{ nullptr };
string data;
LinkNode() = default;
LinkNode(const string& ss) : data(ss) {}
};

class LinkedList
{
private:
LinkNode* front{ nullptr };
LinkNode* rear{ nullptr };
size_t size{ 0 };
void swap(LinkedList& other) noexcept
{
std::swap(front, other.front);
std::swap(rear, other.rear);
std::swap(size, other.size);
}
public:
LinkedList() = default;
~LinkedList()
{
clear();
}
// Copy constructor
LinkedList(const LinkedList& other)
: front(nullptr), rear(nullptr), size(0)
{
LinkNode* cur = other.front;
while (cur)
{
push_back(cur->data);
cur = cur->next;
}
}
// Copy assignment (copy-and-swap)
LinkedList& operator=(const LinkedList& other)
{
if (this == &other) return this;
LinkedList temp(other); // may throw
swap(temp);
return this;
}
void push_back(const string& ss)
{
LinkNode newNode = new LinkNode(ss);
if (rear)
{
rear->next = newNode;
rear = newNode;
}
else
{
front = rear = newNode;
}
++size;
}
string pop_front()
{
if (!front)
{
throw runtime_error("List is empty");
}
LinkNode temp = front;
string retData = front->data;
front = front->next;
if (!front)
{
rear = nullptr;
}
delete temp;
--size;
return retData;
}
string get_front() const
{
if (front==nullptr)
{
throw runtime_error("List is empty");
}
return front->data;
}
void clear()
{
while (front)
{
pop_front();
}
}
void print() const
{
LinkNode* current = front;
while (current)
{
cout << current->data << " ";
current = current->next;
}
cout << endl;
}
size_t get_size() const
{
return size;
}
bool is_empty() const
{
return (size == 0);
}
};

int main()
{
typedef LinkedList Queue;
Queue test_q;
test_q.push_back("first");
test_q.push_back("second");
test_q.push_back("third");
test_q.push_back("fourth");
test_q.print();

cout << "Front element: " << test_q.get_front() << endl;
cout << "Popped element: " << test_q.pop_front() << endl;
test_q.print();
cout << "Queue size: " << test_q.get_size() << endl;
test_q.clear();
cout << "Queue cleared. Size: " << test_q.get_size() << endl;
// Demonstrate copy assignment
Queue q2;
q2 = test_q;
cout << "After assignment, q2 is empty: " << (q2.is_empty() ? "true" : "false") << endl;
cout << "q2 size after assignment: " << q2.get_size() << endl;
return 0;

}