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]

看评论就学到了很多

[chiass]

 /* 更新元素 */
    public void set(int index, int num) {
        if (index < 0 || index >= size)
            throw new IndexOutOfBoundsException("索引越界");
        arr[index] = num;
    }

如果初始化一个链表，

int n = 5;
List<Integer> list = new ArrayList<>(n);
list.set(2,2); // 会提示索引越界；
list.set(0,0); // 赋值正常

这里其实属于一个bug，set方法被认为是更新而非赋值，但是又对0位索引的赋值和更新不做区分。

[krahets]

Hi，ArrayList 是 Java 内置的列表（数组实现）而非链表。

在 Java 的设计中，List list = new ArrayList<>(n); 仅为列表分配了容量，其中没有元素。因此赋值会越界

[HuaWang135608]

JDK17 中 ArrayList 的源代码

    public ArrayList(int initialCapacity) {
        if (initialCapacity > 0) {
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        }
    }

它是懒加载的，构造器中只是设置了容量，size 没有更新，set 的源代码：

    public E set(int index, E element) {
        Objects.checkIndex(index, size);
        E oldValue = elementData(index);
        elementData[index] = element;
        return oldValue;
    }

Objects.checkIndex :

    @ForceInline
    public static
    int checkIndex(int index, int length) {
        return Preconditions.checkIndex(index, length, null);
    }

Preconditions.checkIndex :

    @IntrinsicCandidate
    public static <X extends RuntimeException>
    int checkIndex(int index, int length,
                   BiFunction<String, List<Number>, X> oobef) {
        if (index < 0 || index >= length)
            throw outOfBoundsCheckIndex(oobef, index, length);
        return index;
    }

我不确定你的JDK版本，如果是JDK17的话，这两个 set 应该都是报错的

[HuaWang135608]

忽略懒加载，抱歉，这个不太对

[wupenhu]

one day.

[zccc9527]

There seems to be a problem with shallow copies
貌似存在浅拷贝的问题

[Jiege66a]

void extendCapacity(MyList *nums) {
    // 先分配空间
    int newCapacity = capacity(nums) * nums->extendRatio;
    int *extend = (int *)malloc(sizeof(int) * newCapacity);
    int *temp = nums->arr;

    // 拷贝旧数据到新数据
    for (int i = 0; i < size(nums); i++)
        extend[i] = nums->arr[i];

    // 释放旧数据
    free(temp);

    // 更新新数据
    nums->arr = extend;
    nums->capacity = newCapacity;
}

/* 将列表转换为 Array 用于打印 */
int *toArray(MyList *nums) {
    return nums->arr;
}

新年快乐，想请问一下这个函数的temp指针变量有什么作用，感觉可以不需要它

[krahets]

也可以不用 temp ，直接释放 nums->arr 。不过，这种方法要求在 free(nums->arr); 之后，立即将 nums->arr 更新为新的地址，而且在这两个操作之间不能有任何试图访问 nums->arr 内容的操作，以防止悬挂指针（dangling pointer）引发的问题。

[Jiege66a]

好的，谢谢

[FHMinyi]

/* 构造函数 */
MyList *newMyList() {
    MyList *nums = malloc(sizeof(MyList));
    nums->capacity = 10;
    nums->arr = malloc(sizeof(int) * nums->capacity);
    nums->size = 0;
    nums->extendRatio = 2;
    return nums;
}

请问这里是不是有个bug啊？在vscode里显示MyList *nums = malloc(sizeof(MyList));和nums->arr = malloc(sizeof(int) * nums->capacity);有误，改成MyList *nums = (MyList*)malloc(sizeof(MyList));和nums->arr = (int*)malloc(sizeof(int) * nums->capacity);提示才消除

[Gonglja]

哈喽，

1. 在C中，不需要强制类型转换 malloc 返回的值，返回的 void * 会隐式转换为 MyList *
   
2. 在 C++ 中是不一样的，需要显示转换或使用static_cast
   

关于更详细的信息，可看

1. c void
2. cpp void
3. stackoverflow(https://stackoverflow.com/questions/605845/should-i-cast-the-result-of-malloc)
4. feat(counting_sort): support counting_sort in c/go #431

回到最初的问题，产生这个问题的原因可能是在 vscode 中使用的编译器为 g++

[FHMinyi]

/* 访问元素 */
int get(MyList *nums, int index) {
    assert(index >= 0 && index < nums->size);
    return nums->arr[index];
}

请问这个assert(index >= 0 && index < nums->size);是干嘛的？

[krahets]

安全检查，保证 index 在 index >= 0 && index < nums->size 范围内

[errorMan0125]

这里C的列表实现nums->size 跟 size(nums)应该是一样的效果吧，如果追求规范，大佬们更推荐哪种写法呢？

[krahets]

size(nums) 是我们定义的获取 size 的方法，用它语义更清晰

[errorMan0125]

感谢回复

[hpfish]

func (l *myList) remove(index int) int {
    if index < 0 || index >= l.arrSize {
        panic("索引越界")
    }
    num := l.arr[index]
    // 将索引 index 之后的元素都向前移动一位
    for j := index; j < l.arrSize - 1; j++ {
        l.arr[j] = l.arr[j+1]
    }
    // 更新元素数量
    l.arrSize--
    // 返回被删除的元素
    return num
}

这样删不掉最后一个元素吧？

[AmbitiousJun]

l.arrSize 更新了就代表删掉了吧

[a2635814919]

@hpfish 我们是通过arrSize来访问列表中的元素的，所以虽然最后一个元素没有在物理上删除，但是arrSize的更新使得之前的最后一个元素变得不合法了，从而在逻辑上把最后一个元素删除了

[Alan-Luo-maker]

为什么我在vscode中使用vector<int> nums = { 1, 3, 2, 5, 4 };终端会闪退啊
把这个删掉就立马好了

[BrianChen666]

void delMyList(MyList *nums){
     free(nums->arr);
     free(nums);
}

中free(nums->arr)不是包含在free(nums)中吗？只用后者可以吗？

[krahets]

不可以，free(nums)只会释放结构体nums的内存。如果你不先调用free(nums->arr)来释放数组的内存，那么一旦你释放了结构体本身的内存，你将失去对那部分动态分配数组内存的引用，导致内存泄露。

[Mike23v3]

// C 未提供内置动态数组
这是什么情况

[errorMan0125]

C语言的数组大小是编译时固定长度的，而不是“动态”的

[WalkerInAI]

你好，这句话：
“链表天然可以看作一个列表，其支持元素增删查改操作，并且可以灵活动态扩容。”
会让我感到有歧义，我认为如果链表可以看作是列表，那么链表应可以实现列表的功能。但是在2, 3, 4小点中让我觉得链表并不能实现列表的功能，比如二者访问元素的时间复杂度不一样。
请问是我没有正确理解这句话的含义吗？我的思路错在哪儿？

[Autumn00air]

我的理解是：
链表可以访问元素吗？可以
链表可以增删改查元素吗？可以
最重要的是，链表支持动态扩容。
这些都是列表的功能，也都实现了，你说的访问元素的时间复杂度不一样，但是你要注意的是列表是一种抽象的数据结构概念，它只是定义了有序存储，并且支持增删改查，并没有规定具体实现，更加没有规定时间复杂度，列表不是数组。
数组和链表只是具体的实现结构罢了。
我不知道你是什么语言的，但我看js，作者这里写了用数组来实现列表的过程，实际上，还有一种用链表来实现列表的写法，只是他没写而已。
所以作者说”列表可以基于链表或数组实现。“
（个人理解，欢迎指正~）

[krahets]

Hi，“可以实现”和“高效实现”是两个层面上的概念。从“可以实现”的角度看，数组和链表都可以用来实现列表；从效率上看，数组和链表实现的列表的“增删查改”的效率是不同的，呈现互补的特点。

[WalkerInAI]

感谢回复。
抱歉我没有交代清楚这边的情况，我正在学习的编程语言是Python，现阶段水平刚过新手村（刚学完《Python编程：从入门到实践第2版》），刚刚接触GitHub。
我是否应该这样理解，因为链表都具备列表对应的功能，例如有序存储，可访问元素，可增删差改元素，因此链表 可以实现 列表这类数据结构。（如果我理解正确，请无需回复我；如果我的理解还是存在问题，恳请再次回复）

[estarpro1022]

Java列表的实现中，是不是没有做缩容的操作(doge

[krahets]

没有做。实际上，Java 的 ArrayList 也不会自动缩容，但可以通过调用 ArrayList 的 trimToSize() 方法来实现缩容

[ruomu007]

c++ sort函数的区间是左闭右开的， sort(nums.begin(), nums.end()) ， nums.end()指向的最后一个元素外的一个地址，所以是对nums的所有元素排序。 但是 sort(nums.begin(), nums.begin()+8)，因为左闭右开，取不到第8个元素，应该只是对前7个元素排序吧，可是运行的结果是对前8个元素排序了。 请问如何理解这个左闭右开

[errorMan0125]

nums.begin() + 8 这个是&nums[0]偏移了8个元素了也就是&nums[8]，可以打印下nums.end()跟nums.begin() + 8对比下？

[ruomu007]

sort(nums.begin(), nums.begin()+8) 能取到8个。 但是sort(nums.begin(), nums.end()) 只是取到了最一个元素，但实际上 nums.end()表示的是 最有一个元素外的元素。 这样 就不一致了， 照理说sort(nums.begin(), nums.end()) 应能取到最后一个元素外的一个元素，但是实际没有。

[errorMan0125]

但实际上 nums.end() 表示的是 最右一个元素外的元素
照理说sort(nums.begin(), nums.end()) 应能取到最后一个元素外的一个元素 但是实际没有

我这里的nums.end()是可以取到 数组最后一个元素再偏移一位的，这边是拿官方的代码改了下

[linzha0]

十分感谢！我在手动敲打每行代码学习。好像发现一个无关紧要的小问题，my_list.cpp, line159,这个注释里，好像应该是在 i = 4会导致容量超出。

[linzha0]

list nums = [1, 3, 2, 5, 4]
capacity = 10 ，size = 5
at index 3 insert 6 , get nums = [1, 3, 2, 6, 5, 4]
remove at index=3 element, get nums = [1, 3, 2, 5, 4]
index=1, size: 5access index = 1 element, get num = 3
update element at index = 1 to 0, get nums = [1, 0, 2, 5, 4]
extened list nums = [1, 0, 2, 5, 4, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
capacity = 20 , size = 15

[SEELE0]

大佬好，可否在这里添加 C语言通过malloc 申请分配内存的 方式作为动态数组实现呢

[SEELE0]

抱歉看书不仔细 没看到最后已经提供了