初稿：2017-11-19 13:05:57
4种链表
- 不循环单链表：加头结点，使得插入删除操作相同，不必特别处理插入或删除的是第一个位置的情况。
- 循环单链表：引用参数是最后一个结点的指针pTail，这样既能迅速找到首结点pHead = pTail->next，也能迅速获取表尾。
- 不循环双向链表：p所指结点后插入结点q. q->next = p->next; p->next->pre = q; p->next = q; q->pre = p;
- 循环双向链表：引用参数首或尾都可。
链表和数组的区别
数组初始容量一旦确定，不能再改变，适合要处理的数据量已知的情况。
未知要处理的数据量使用数组，可能造成空间浪费或容量不足，虽然有动态数组可扩容，但是频繁扩容会使系统产生很大的开销。
链表容量不限，长度与元素个数相同，但是需要额外的空间存放下一元素的地址，空间使用率不如数组。
按index查找，数组存取元素时间复杂度是O（1），链表是O（n）
链表插入和删除时间复杂度是O（1），数组是O（n）
查找值是value的某个元素，速度则相同。
内容来源于网络如有侵权请私信删除
- 还没有人评论，欢迎说说您的想法！
客服
