[Arch] Java数据结构与算法 - 链表

博客首页 » Arch Java数据结构与算法 - 链表

发布于 20 Jul 2015 08:27
标签 blog
通过链的形式将元素串在一起,链表提供了对于插入、修改灵活的数据存储方式。

链表

单链表 Link List

next
insertFirst()
deleteFirst()

find(v)
delete(v)

双端链表 First Last List

insertLast()
deleteLast()

链表效率

表头插入删除都很快 O(1)
查找、删除、指定位置后插入需要比较次数 O(N)
不需要复制/移动
可以扩展,使用所有空间

有序链表 Sorted List

插入/删除 N/2次,既 O(N)
用作排序,复制次数少,但是效率依然是 O(N^2)

ADT

设计原则,不干扰用户的情况下,修改实现方法。

双向链表 Double Linked List

next
previous

deleteFirst()
deleteLast()
deleteKey(key)

双向双端链表

可以容易、高效地实现双端插入删除

迭代器

Node current
Node previous
LinkList list

reset()
nextNode()
getCurrent()
atEnd()
insertAfter()
insertBefore()
deleteCurrent()

find(v)
replace()

当删除的时候,迭代器应该指向下一个节点,如果到达表尾,则回到表头是一个选择。

在C++中,迭代器和链表,是通过把迭代器设为链表的友元来实现的。

循环链表

因为尾指向头,所以没有头尾。

step()


本页面的文字允许在知识共享 署名-相同方式共享 3.0协议和GNU自由文档许可证下修改和再使用,仅有一个特殊要求,请用链接方式注明文章引用出处及作者。请协助维护作者合法权益。


系列文章

文章列表

  • Arch Java数据结构与算法 - 链表

这篇文章对你有帮助吗,投个票吧?

rating: 0+x

留下你的评论

Add a New Comment