赞
踩
单链表:结点中只有一个指针的链表称为单链表,这是最简单的链表结构。
其节点由两部分构成:
双链表:有前后两个指针的链表。
其节点由三部分构成:
单链表插入节点主要分两步,顺序不可替换:
1.先将x->next指向A2
2.再将A1->next指向x
删除节点其实只需要一步
A1->next 指向A3就行,此时A2会被自动回收
通过对单链表的分析,可以看出单链表有如下缺点:
- 单链表的查找方法只能是一个方向
- 单链表不能自我删除,需要靠上一节点进行辅助操作。
双链表的操作会比单链表复杂很多,顺序也可以是2143,其他的可以自己想一想,只要不断就行。
- x->next指向A2
- A1->next指向x
- x->prev指向A1
- A2->prev指向x
删除节点容易很多,先后顺序也不是很重要
A3->prev指向A1
A1->next指向A3
以下内容参考Java LinkedList。更详细可以去这里看。
现在来讲Java要用到链表应该怎么写。
ArrayList和LinkedList都实现了链表,两者的区别在于与 ArrayList 相比,LinkedList 的增加和删除的操作效率更高,而查找和修改的操作效率较低。
链表用LinkedList较多。
LinkedList 类位于 java.util 包中,使用前需要引入它,语法格式如下:
// 引入 LinkedList 类
import java.util.LinkedList;
LinkedList<E> list = new LinkedList<E>(); // 普通创建方法
或者
LinkedList<E> list = new LinkedList(Collection<? extends E> c); // 使用集合创建链表
创建一个简单的链表实例:
import java.util.LinkedList;
public class RunoobTest {
public static void main(String[] args) {
LinkedList<String> sites = new LinkedList<String>();
sites.add("Google");
sites.add("Runoob");
sites.add("Taobao");
sites.add("Weibo");
System.out.println(sites);
}
}
以上实例,执行输出结果为:
[Google, Runoob, Taobao, Weibo]
其他操作可参考这个表格
方法 | 描述 |
---|---|
addFirst() | 在表头增加一个元素 |
addLast() | 在表尾增加一个元素 |
removeFirst() | 从表头移除一个元素 |
removeLast() | 从表尾移除一个元素 |
getFirst() | 获得表头的元素 |
getLast() | 获得表尾的元素 |
想看Java中链表是如何实现以及基本的操作可以看这个博客,讲的很清楚,我就不在这里贴代码了。java ListNode 链表
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。