Java-链表结构

  • 内容
  • 评论
  • 相关

链表结构(火车和火车车厢):

1):单向链表:只能从头遍历到尾/只能从尾遍历到头.

2):双向链表:既可以从头遍历到尾,又可以从尾遍历到头.

-------------------------------------

通过引用来表示上一个节点和下一个节点的关系.

对LinekdList操作的性能分析:

1):增加操作:

双向链表可以直接获取自己的第一个和最后一个节点,

如果新增的元素在第一个或最后一个位置,那么操作只有1次.

2):删除操作(removeFisrt,removeLast):

如果删除第一个元素: 操作一次.

如果操作最后一个元素:操作一次.

如果删除中间的元素:

找到元素节点平均操作:(1+N)/2次.

找到节点之后做删除操作: 1次.

3):查询操作:

平均:(N+1)/2次

4):修改操作:

平均:(N+1)/2次

基于数组的列表和基于链表的列表的性能对比:

ArrayList:查询,更改较快,新增和删除较慢.

LinkedList:查询,更改较慢,新增和删除较快.

评论

0条评论

发表评论

电子邮件地址不会被公开。 必填项已用*标注