1.STL容器—list使用技巧
2.数据结构编程求救
3.C#浅析C# List实现原理

STL容器—list使用技巧

       列表容器(list)在STL中是源码一种序列容器，特点是代码非连续内存分配。对比vector，源码其查找操作通常较慢，代码但插入和删除操作速度较快。源码列表通常实现为双向链表，代码java开发签到源码这为实现单链表提供了便利。源码通过双向链接，代码可在常数时间内进行插入和删除操作，源码但查找操作需遍历整个列表，代码时间复杂度为O(n)。源码

       查看上图，代码可了解std::list在内存中的源码布局，列表中的代码元素通过双向链接结点存储，每个结点包含数据和指向前后结点的源码指针。

       列表的查找操作耗时，一旦找到元素，后续操作如更新、插入或删除则为常数时间复杂度。从性能角度看，list并不总是源码变为反码最佳选择，但在某些场景下仍具有优势。

       以下代码展示了如何使用list进行内存分配测试，结果显示list的内存分配与vector不同，不会在插入元素时进行内存重新分配和数据拷贝。

       清理list内存通常较为复杂。std::list自身并未提供内存释放接口，且标准库不保证立即释放内存。只有vector和string容器支持类似std::vector的swap函数，以在清理内存时立即释放空间。例如，源码vip论坛chromium.org源代码中的stl_util.h文件中的清理代码仅适用于vector和string。

       尽管在多数情况下std::list似乎并不突出，它在某些特定场景中仍具有用武之地。例如，当需要频繁插入和删除元素，而访问元素的顺序不固定时，list可能是更优选择。此外，当处理大量数据且内存使用效率是关键因素时，list的烈火雄心源码特性也能带来优势。因此，在权衡效率和特定需求后，list仍值得在编程实践中考虑。

数据结构编程求救

       试验一:

       #include<iostream>

       #include<string>

       using namespace std;

       struct List

       {

        int num;

        List *next;

       };

       List *head=NULL;

       List* CreateList()

       {

        List *pL;

        List *pEnd;

        pL=new List;

        head=pL;

        pEnd=pL;

        cout<<"请输入节点的数目,以 0 结束"<<endl;

        cin>>pL->num;

        while(pL->num!=0)

        {

        pEnd->next=pL;

        pEnd=pL;

        pL=new List;

        cin>>pL->num;

        }

        delete pL;

        pEnd->next=NULL;

        return head;

       }

       void ShowList(List *head)

       {

        cout<<endl;

        cout<<"链表节点如下:"<<endl;

        while(head)

        {

        cout<<head->num<<endl;

        head=head->next;

        }

       }

       void InsertList(List *head,int num)

       {

        List *list =new List;

        List *l;

        while(head)

        {

        l=head;

        head=head->next;

        }

        list->num=num;

        list->next=NULL;

        l->next=list;

       }

       void DeleteList(List *head, int num)

       {

       List *l;

        if(head->num==num)

        {

        l=head;

        head=head->next;

        ::head=head;

        delete l;

        return ;

        }

        List *l1=head;

        while(head)

        {

        if(head->next==NULL){

        cout<<"找不到不要删除的数字."<<endl;

        return ;

        }

        if(head->next->num==num)

        {

        l=head->next;

        head->next=l->next;

        delete l;

        ::head=l1;

        cout<<"操作成功"<<endl;

        return ;

        }

        head=head->next;

        }

        cout<<"找不到不要删除的数字."<<endl;

       }

       int GetListNum(List *head)

       {

        int num=0;

        while(head)

        {

        num++;

        head=head->next;

        }

        return num;

       }

       int main()

       {

        string str;

       begin:

        cout<<"1->增加链表 2->显示链表 3->插入节点 4->删除节点 5->节点数目"<<endl;

        cin>>str;

        if(str[0]=='1')

        {

        CreateList();

        }

        else if(str[0]=='2')

        {

        if(head==NULL)

        {

        cout<<"你的链表现在是空的,请增加链表"<<endl;

        getchar();

        getchar();

        system("cls");

        goto begin;

        }

        ShowList(head);

        }

        else if(str[0]=='3')

        {

        if(head==NULL)

        {

        cout<<"你的链表现在是空的,请增加链表"<<endl;

        getchar();

        getchar();

        system("cls");

        goto begin;

        }

        int num;

        cout<<"请输入要插入的数字:"<<endl;

        cin>>num;

        InsertList(head,num);

        }

        else if(str[0]=='4')

        {

        if(head==NULL)

        {

        cout<<"你的链表现在是空的,请增加链表"<<endl;

        getchar();

        getchar();

        system("cls");

        goto begin;

        }

        int num;

        cout<<"请输入要删除的数字:"<<endl;

        cin>>num;

        DeleteList(head,num);

        }

        else if(str[0]=='5')

        {

        cout<<"节点数是:"<<GetListNum(head)<<endl;

        }

        else

        {

        cout<<"输入错误,请重新输入.";

        }

        if(str[0]!='Q' && str[0]!='q'){

        cout<<endl<<endl;

        getchar();

        getchar();

        system("cls");

        goto begin;

        }

       }

       试验二:

       #include<iostream>

       #include<string>

       using namespace std;

       struct Stack {

        char c;

        Stack *pNext;

       };

       void InitStack(Stack *&s)

       {

        s=NULL;

       }

       char Peek(Stack *s)

       {

        if(s==NULL) {

        cout<<"栈是空的."<<endl;

        return -1;

        }

        return s->c;

       }

       void Push(Stack *&s,Stack *newS)

       {

        newS->pNext=s;

        s=newS;

       }

       char Pop(Stack *&s)

       {

        if(s==NULL)

        {

        cout<<"栈是空的."<<endl;

        return -1;

        }

        Stack *pNext;

        char c;

        if(s)

        {

        pNext=s->pNext;

        c=s->c;

        delete s;

        s=pNext;

        return c;

        }

       }

       int main()

       {

        Stack *s;

        Stack *s1;

        InitStack(s);

        long num;

        int m;

        int k;

        char c;

        cout<<"输入一个数:"<<endl;

        cin>>num;

        cout<<"输入要转换的进制:"<<endl;

        cin>>k;

        while(num!=0)

        {

        m=num%k;

        c=(int('0')+m);

        s1=new Stack;

        s1->c=c;

        Push(s,s1);

        num/=k;

        }

        while(s)

        {

        cout<<Pop(s);

        }

        cout<<endl;

       }

C#浅析C# List实现原理

       C# List 实现原理详解

       在面试中，我被问到List的初始化容量问题，暴露了自己在C#编程中的不足。List作为C#中最常见的可伸缩数组组件，常用于替代数组，其可扩展性避免了手动分配数组大小的麻烦，甚至有时作为链表使用。qzxing 源码解读那么，它底层的工作机制如何呢？我们来深入了解其添加、插入、删除、索引操作以及排序等方面的实现。

       Add操作

       在添加元素前，List会调用EnsureCapacity确保有足够的空间，如果容量不够，会按需扩容，初始容量为4，每次扩张都是翻倍：4, 8, , ...。然而，List使用数组作为底层数据结构，虽然索引访问快，扩容时会产生新的数组，造成内存浪费和GC压力。

       Insert操作

       插入操作涉及Array.Copy，将指定索引后的元素后移，时间复杂度为O(n)。这可能导致性能降低和内存冗余。

       Remove操作

       删除元素时，同样通过Array.Copy将指定索引后的元素前移，O(n)复杂度。删除元素后，后续元素需要移动，增加了内存消耗和GC负担。

       索引访问与Find

       直接使用数组下标访问速度快，但Find的线性查找可能导致O(n)效率。在Unity中，foreach可能导致额外的GC，尽管Unity5.5已解决这个问题，但仍需注意foreach可能增加垃圾对象。

       Clear操作

       Clear并不会删除数组，仅清零元素并设_size为0，表示容量为0，避免内存浪费。

       foreach与Sort

       foreach在Unity中可能增加额外GC，但已在新版本中解决。List的Sort使用快速排序，时间复杂度为O(nlogn)。

       总结与参考

       深入理解List的实现原理，对提高C#编程效率至关重要。参考《Unity3D高级编程之进阶主程》第一章和List源码(list.cs)，以优化代码和避免不必要的性能损失。