系列文章目录
集合及数据结构第七节————LinkedList的模拟实现与使用
LinkedList的模拟实现与使用
- 无头双向链表实现
- 什么是LinkedList
- LinkedList的使用
- LinkedList的遍历
- ArrayList和LinkedList的区别
文章目录
一、LinkedList的模拟实现
1.无头双向链表实现
定义接口
public interface Ilist {
public void addFirst(int data);//头插法
public void addLast(int data);//尾插法
public void addIndex(int index,int data);//任意位置插入,第一个数据节点为0号下标
public boolean contains(int key);//查找是否包含关键字key是否在双向链表当中
public void remove(int key);//删除第一次出现关键字为key的节点
public void removeAllKey(int key); //删除所有值为key的节点
public int size();//得到双向链表的长度
public void clear() ;//清空链表
public void display() ;//打印链表
}
定义双向链表的内部类
static class ListNode {//将节点定义成内部类
public int val;//数据域
public ListNode next;//后驱节点（引用类型）
public ListNode prev;//前驱节点
public ListNode(int val) {
this.val = val;
//没有初始化next默认为null（因为next是引用数据类型）
}
}
public ListNode head;//头节点
public ListNode last;//尾节点
接口的实现
头插法的时间复杂度为O（1）
头插法
思路：
第一次插入时head和last都指向这个节点
代码实现：
public void addFirst(int data) {;//头插法
ListNode node = new ListNode(data);//创建一个node节点用来存放插入的数据
if(head == null){//插入第一个数据
this.head = node;
this.last = node;
}else {//有其他节点，进行头插
node.next = this.head;//先绑定后面更安全
this.head.prev = node;
this.head = node;
}
}
尾插法
尾插法的时间复杂度为O（1）
思路：
第一次插入时head和last都指向这个节点
代码实现：
public void addLast(int data) {//尾插法
ListNode node = new ListNode(data);//创建一个node节点用来存放插入的数据
if(head == null){//插入第一个数据
this.head = node;
this.last = node;
}else {//有其他节点，进行尾插
last.next = node;//先绑定后面更安全
node.prev = this.last;
this.last = node;
}
}
任意位置插入,第一个数据节点为0号下标
思路：
- 检查index是否合法
- 找到cur节点（cur走index步 ）（新增一个private修饰的searchIndex方法来找到index位置节点）
- 插入node节点
public class AddIndexLocationWrong extends RuntimeException{// 检查index是否合法（输入下标不合法）
public AddIndexLocationWrong(String message){
super(message);
}
}
private ListNode searchIndex(int index){//找到index位置节点
ListNode cur = this.head;//创建一个临时节点来替head节点完成工作
//从而避免head = null的情况出现
while (index != 0){
cur = cur.next;//让cur指向下一个节点
index--;
}
return cur;
}
public void addIndex(int index, int data) {;//任意位置插入,第一个数据节点为0号下标
int len = size();
if(index < 0 || index > len){//如果输入的index对应节点没有数据，抛出异常
throw new AddIndexLocationWrong("输入的index位置不合法" + index);
}
if (index == 0) {//在开头插入直接调用头插法
addFirst(data);
return;
}
if (index == len){//在结尾插入，直接调用尾插法
addLast(data);
return;
}
ListNode cur = searchIndex(index);//新建一个cur节点存放找到的index位置的节点
ListNode node = new ListNode(data);//创建一个node节点用来存放插入的数据
//插入数据（先修改next就一定不会出错）
node.next = cur;//让node的next后驱指向cur
cur.prev.next = node;//让插入前cur的前一个节点的next后驱指向node
node.prev = cur.prev;//让node的next前驱指向插入前cur的前一个节点
cur.prev = node;//让cur的next前驱指向node
}
查找是否包含关键字key是否在双向链表当中
public boolean contains(int key) {//查找是否包含关键字key是否在单链表当中
ListNode cur = this.head;//创建一个临时节点来替head节点完成工作
//从而避免head = null的情况出现
while (cur != null){
if (cur.value == key){
return true;
}
cur = cur.next;
}
return false;
}
删除第一次出现关键字为key的节点
思路：
一般情况下
删除的是第一个节点
删除最后一个节点
代码实现：
public void remove(int key) {//删除第一次出现关键字为key的节点
ListNode cur = this.head;
while (cur != null){
if(cur.val ==key) {//cur的val与key相等时
if(cur == head){//删除的是第一个节点
head = head.next;//头节点向后移动（当链表中只有一个节点时，相当于把head置空让第一个节点不再被head引用）
if (head == null){//当链表中只有一个节点时
// （不加这个判断条件会导致else中的语句在只有一个节点时,空指针异常）
last = null;//当链表中只有一个节点时,last置空让第一个节点不再被last引用
}else {
head.prev = null;//移动后的头节点的前驱置空（第一个节点不在被引用，会被自动化回收）
}
}else {//删除的不是第一个节点
cur.prev.next = cur.next;//让cur的前一个节点的next后驱指向cur的后一个节点
if(cur.next == null){//删除的是最后一个节点,把last置空让第一个节点不再被last引用
last = last.prev;
}else {//删除的是中间节点
cur.next.prev = cur.prev;//让cur的后一个节点的前驱指向cur的前一个节点
}
}
return;//删除结束后退出
}
else {
cur = cur.next;
}
}
}
删除所有值为key的节点
public void removeAllKey(int key) { //删除所有值为key的节点
ListNode cur = this.head;
while (cur != null){
if(cur.val ==key) {//cur的val与key相等时（删完一个后不退出，直到遍历完整个链表）
if(cur == head){//删除的是第一个节点
head = head.next;//头节点向后移动（当链表中只有一个节点时，相当于把head置空让第一个节点不再被head引用）
if (head == null){//当链表中只有一个节点时
// （不加这个判断条件会导致else中的语句在只有一个节点时,空指针异常）
last = null;//当链表中只有一个节点时,last置空让第一个节点不再被last引用
}else {
head.prev = null;//移动后的头节点的前驱置空（第一个节点不在被引用，会被自动化回收）
}
}else {//删除的不是第一个节点
cur.prev.next = cur.next;//让cur的前一个节点的next后驱指向cur的后一个节点
if(cur.next == null){//删除的是最后一个节点,把last置空让第一个节点不再被last引用
last = last.prev;
}else {//删除的是中间节点
cur.next.prev = cur.prev;//让cur的后一个节点的前驱指向cur的前一个节点
}
}
}
cur = cur.next;
}
}
得到双向链表的长度
ListNode cur = this.head;//创建一个临时节点来替head节点完成工作
//从而避免head = null的情况出现
int count = 0;//用来计数
while (cur != null){
count++;
cur = cur.next;
}
return count ;
清空
- 直接把头节点和尾节点置空（不推荐）
- 把每个节点的每个域都置空
public void clear() {//清空链表
ListNode cur = head;
while (cur != null){
ListNode temp = cur.next;//让temp指向cur的后驱指向的节点，让清空操纵正常进行
//cur.val = null;//
cur.prev = null;
cur.next = null;
cur = temp;
}
head = null;
last = null;
}
打印链表的数据
要创建一个临时节点来替head节点完成工作，从而避免head = null的情况出现
public void display() {//打印链表的数据
ListNode cur = this.head;//创建一个临时节点来替head节点完成工作
//从而避免head = null的情况出现
while (cur != null){//打印的停止条件
System.out.print(cur.value + " ");
cur = cur.next;//让head指向下一个节点
}
System.out.println();
}
二、.LinkedList的使用
1.什么是LinkedList
LinkedList的底层是双向链表结构(链表后面介绍)，由于链表没有将元素存储在连续的空间中，元素存储在单独的节点中，然后通过引用将节点连接起来了，因此在在任意位置插入或者删除元素时，不需要搬移元素，效率比较高。
在集合框架中，LinkedList也实现了List接口，具体如下：
【说明】
- LinkedList实现了List接口
- LinkedList的底层使用了双向链表
- LinkedList没有实现RandomAccess接口，因此LinkedList不支持随机访问
- LinkedList的任意位置插入和删除元素时效率比较高，时间复杂度为O(1)
- LinkedList比较适合任意位置插入的场
2.LinkedList的使用（ * * ）
1. LinkedList的构造
public static void main(String[] args) {
// 构造一个空的LinkedList
List<Integer> list1 = new LinkedList<>();
List<String> list2 = new java.util.ArrayList<>();
list2.add("JavaSE");
list2.add("JavaWeb");
list2.add("JavaEE");
// 使用ArrayList构造LinkedList
List<String> list3 = new LinkedList<>(list2);
}
2. LinkedList的其他常用方法介绍
| 方法 | 解释 |
|---|---|
| void addLast(E e) | 尾插 e |
| void add(int index, E element) | 将 e 插入到 index 位置 |
| boolean addAll(Collection<? extends E> c) | 尾插 c 中的元素 |
| E remove(int index) | 删除 index 位置元素 |
| boolean remove(Object o) | 删除遇到的第一个 o |
| E get(int index) | 获取下标 index 位置元素 |
| E set(int index, E element) | 将下标 index 位置元素设置为 element |
| void clear() | 清空 |
| boolean contains(Object o) | 判断 o 是否在链表中 |
| int indexOf(Object o) | 返回第一个 o 所在下标 |
| int lastIndexOf(Object o) | 返回最后一个 o 的下标 |
| List< E > subList(int fromIndex, int toIndex) | 截取部分 list |
（? extends E）是指 ：？是不是E本身或者E的子类
首先创建一个Integer类型的链表表并存入一些数字，并打印一下链表的大小和链表
inkedList<Integer> list = new LinkedList<>();
list.add(1); // add(elem): 表示尾插
list.add(2);
list.add(3);
list.add(4);
list.add(5);
list.add(6);
list.add(7);
System.out.println(list.size());
System.out.println(list);
在起始位置插入0
list.add(0, 0); // add(index, elem): 在index位置插入元素elem
System.out.println(list);
remove(): 删除第一个元素，内部调用的是removeFirst()
list.remove(); // remove(): 删除第一个元素，内部调用的是removeFirst()
System.out.println(list);
removeFirst(): 删除第一个元素
list.removeFirst(); // removeFirst(): 删除第一个元素
System.out.println(list);
removeLast(): 删除最后元素
list.removeLast(); // removeLast(): 删除最后元素
System.out.println(list);
remove(index): 删除index位置的元素
list.remove(1); // remove(index): 删除index位置的元素
System.out.println(list);
contains(elem): 检测elem元素是否存在，如果存在返回true，否则返回false
if(!list.contains(1)){//1如果不存在就进入if
list.add(0, 1);
}
list.add(1);//内部调用的是linkLast(e);
System.out.println(list);
indexOf(elem): 从前往后找到第一个elem的位置
System.out.println(list.indexOf(1)); // indexOf(elem): 从前往后找到第一个elem的位置
lastIndexOf(elem): 从后往前找第一个1的位置
System.out.println(list.lastIndexOf(1)); // lastIndexOf(elem): 从后往前找第一个1的位置
get(index): 获取指定位置元素
int elem = list.get(0); // get(index): 获取指定位置元素
System.out.println(elem);
set(index, elem): 将index位置的元素设置为elem
list.set(0, 100); // set(index, elem): 将index位置的元素设置为elem
System.out.println(list);
subList(from, to): 用list中[from, to)之间的元素构造一个新的LinkedList返回
List<Integer> copy = list.subList(0, 3);
System.out.println(list);
System.out.println(copy);
copy.add( 0,5656);
System.out.println(list);
System.out.println(copy);
将list中元素清空
list.clear(); // 将list中元素清空
System.out.println(list.size());
完整代码：
public static void main(String[] args) {
LinkedList<Integer> list = new LinkedList<>();
list.add(1); // add(elem): 表示尾插
list.add(2);
list.add(3);
list.add(4);
list.add(5);
list.add(6);
list.add(7);
System.out.println(list.size());
System.out.println(list);
// 在起始位置插入0
list.add(0, 0); // add(index, elem): 在index位置插入元素elem
System.out.println(list);
list.remove(); // remove(): 删除第一个元素，内部调用的是removeFirst()
list.removeFirst(); // removeFirst(): 删除第一个元素
list.removeLast(); // removeLast(): 删除最后元素
list.remove(1); // remove(index): 删除index位置的元素
System.out.println(list);
// contains(elem): 检测elem元素是否存在，如果存在返回true，否则返回false
if(!list.contains(1)){
list.add(0, 1);
}
list.add(1);
System.out.println(list);
System.out.println(list.indexOf(1)); // indexOf(elem): 从前往后找到第一个elem的位置
System.out.println(list.lastIndexOf(1)); // lastIndexOf(elem): 从后往前找第一个1的位置
int elem = list.get(0); // get(index): 获取指定位置元素
list.set(0, 100); // set(index, elem): 将index位置的元素设置为elem
System.out.println(list);
// subList(from, to): 用list中[from, to)之间的元素构造一个新的LinkedList返回
List<Integer> copy = list.subList(0, 3);
System.out.println(list);
System.out.println(copy);
list.clear(); // 将list中元素清空
System.out.println(list.size());
}
3.LinkedList的遍历
ArrayList 可以使用三方方式遍历：for循环+下标、foreach、使用迭代器
public static void main(String[] args) {
LinkedList<Integer> list = new LinkedList<>();
list.add(1); // add(elem): 表示尾插
list.add(2);
list.add(3);
list.add(4);
list.add(5);
list.add(6);
list.add(7);
System.out.println(list.size());
//for循环+下标遍历
for (int i = 0; i < list.size(); i++) {
System.out.print(list.get(i) + " ");
}
System.out.println();
// foreach遍历
for (int e:list) {
System.out.print(e + " ");
}
System.out.println();
// 使用迭代器遍历---正向遍历 要导包--》import java.util.ListIterator;
ListIterator<Integer> it = list.listIterator();
while(it.hasNext()){
System.out.print(it.next()+ " ");
}
System.out.println();
// 使用反向迭代器---反向遍历 要导包--》import java.util.ListIterator;
ListIterator<Integer> rit = list.listIterator(list.size());
while (rit.hasPrevious()){
System.out.print(rit.previous() +" ");
}
System.out.println();
}
三、ArrayList和LinkedList的区别
如果经常根据下标进行查找的，可以使用顺序表Array list。
如果经常进行插入和删除的，可以使用链表Linked list。
