java 数据结构入门到入土——链表（完）LinkedList

目录

一，双向链表

1.单向链表的缺点

2.什么是双向链表？

3.自主实现双向链表

接口实现：

二，LinkedList

1.LinkedList的使用

1.1 什么是LinkedList？

1.2 LinkedList的使用

1.LinkedList的构造

2.LinkedList的其它常用方法介绍

3.LinkedList的遍历

三，ArrayList与LinkedList的区别

一，双向链表

1.单向链表的缺点

再了解单向链表的实现以及使用过后，我们发现单项链表存在存在缺点：

1.如下图，当cur访问下一个节点时无法再访问到上一个节点

2.尾插法的时间复杂度为O(N)

为应对该类问题，于是就有了双向链表

2.什么是双向链表？

定义：双向链表由一系列的节点组成，每个节点包含两个指针，分别指向前一个节点和后一个节点。与单向链表不同，双向链表可以从任意节点开始，向前或向后遍历链表。

如下图所示：

这是一个无头双向链表，从中我们不难看出它与无头单向链表的区别：

1.不仅有头节点通过next进行顺序访问，还有尾节点通过prev进行逆序访问

2.额外有一个prev域访问上一个已访问过的节点

3.自主实现双向链表

接口实现：

接口部分：

public interface IList {

//头插法

public void addFirst(int data);

//尾插法

public void addLast(int data);

//任意位置插入,第一个数据节点为0号下标

public void addIndex(int index, int data);

//查找是否包含关键字key是否在单链表当中

public boolean contains(int key);

//删除第一次出现关键字为key的节点

public void remove(int key);

//删除所有值为key的节点

public void removeAllKey(int key);

//得到单链表的长度

public int size();

//打印单链表

public void display();

//清空单链表

public void clear();

}

接口重写部分：

public class MyList implements IList{

static class ListNode {

public int val;//值

public ListNode prev;//访问上一个域

public ListNode next;//访问下一个域

public ListNode(int val) {

this.val = val;

}

}

public ListNode head;//头节点

public ListNode last;//尾节点

//头插法

@Override

public void addFirst(int data) {

ListNode node = new ListNode(data);

if (this.head == null) {

this.head = node;

this.last = node;

} else {

node.next = this.head;

this.head.prev = node;

this.head = node;

}

}

//尾插法

@Override

public void addLast(int data) {

ListNode node = new ListNode(data);

if (this.head == null) {

this.head = node;

this.last = node;

} else {

this.last.next = node;

node.prev = this.last;

this.last = node;

}

}

//任意位置插入,第一个数据节点为0号下标

@Override

public void addIndex(int index, int data) {

ListNode node = new ListNode(data);

ListNode cur = this.head;

if (index >= 0 && index <= size()) {

if (index == 0) {

addFirst(data);

return;

}

if (index == size()) {

addLast(data);

return;

}

int count = 1;

while (cur != null) {

ListNode curNext = cur.next;

if (count == index) {

node.next = curNext;

curNext.prev = node;

cur.next = node;

node.prev = cur;

}

count++;

cur = cur.next;

}

} else {

throw new IndexException("添加下标异常！");

}

}

//查找是否包含关键字key是否在单链表当中

@Override

public boolean contains(int key) {

ListNode cur = this.head;

while (cur != null) {

if (cur.val == key) {

return true;

}

cur = cur.next;

}

return false;

}

//删除第一次出现关键字为key的节点

@Override

public void remove(int key) {

ListNode cur = this.head;

while (cur != null) {

ListNode curNext = cur.next;

if (cur.val == key) {

//删头节点

if (cur.prev == null) {

//this.head.val = null;

this.head = head.next;

head.prev = null;

return;

}

//删尾节点

if (cur.next == null) {

//this.last.val == null;

this.last = last.prev;

last.next = null;

return;

}

curNext.prev = cur.prev;

cur.prev.next = curNext;

return;

}

cur = cur.next;

}

}

@Override

public void removeAllKey(int key) {

ListNode cur = this.head;

while (cur != null) {

ListNode curNext = cur.next;

if (cur.val == key) {

//删头节点

if (cur.prev == null) {

//this.head.val = null;

this.head = head.next;

head.prev = null;

} else if (cur.next == null) {

//this.last.val == null;

this.last = last.prev;

last.next = null;

} else {

curNext.prev = cur.prev;

cur.prev.next = curNext;

}

}

cur = cur.next;

}

}

//得到单链表的长度

@Override

public int size() {

ListNode cur = this.head;

int count = 0;

while (cur != null) {

count++;

cur = cur.next;

}

return count;

}

//打印单链表

@Override

public void display() {

ListNode cur = this.head;

if (head == null) {

System.out.println("[" + "]");

} else {

System.out.print("[");

while (cur != null) {

if (cur == last) {

System.out.print(cur.val);

} else {

System.out.print(cur.val + " ");

}

cur = cur.next;

}

System.out.println("]");

}

}

//清空单链表

@Override

public void clear() {

ListNode cur = this.head;

while (cur.next != null) {

ListNode curNext = cur.next;

//cur.val =null;

cur.prev = null;

cur.next = null;

}

this.head = null;

this.last = null;

}

}

二，LinkedList

LinkedList是一个双向链表，以上双向链表便是模拟LinkedList

1.LinkedList的使用

1.1 什么是LinkedList？

LinkedList的官方文档

LinkedList的底层是双向链表结构，由于链表没有将元素存储在连续的空间中，元素存储在单独的节点中，然后通过引用将节点连接起来了，因此在在任意位置插入或者删除元素时，不需要搬移元素，效率比较高。

在集合框架中，LinkedList也实现了List接口

【说明】

1. LinkedList实现了List接口

2. LinkedList的底层使用了双向链表

3. LinkedList没有实现RandomAccess接口，因此LinkedList不支持随机访问

4. LinkedList的任意位置插入和删除元素时效率比较高，时间复杂度为O(1)

5. LinkedList比较适合任意位置插入的场景

1.2 LinkedList的使用

1.LinkedList的构造

方法

解释

LikedList()

无参构造

public LinkedList(Collection c)

使用其他集合容器中元素构造

List

public static void main(String[] args) {

// 构造一个空的LinkedList

List list1 = new LinkedList<>();

List list2 = new java.util.ArrayList<>();

list2.add("JavaSE");

list2.add("JavaWeb");

list2.add("JavaEE");

// 使用ArrayList构造LinkedList

List list3 = new LinkedList<>(list2);

}

2.LinkedList的其它常用方法介绍

方法

解释

boolean

add

(E e)

尾插

e

void

add

(int index, E element)

将

e

插入到

index

位置

boolean

addAll

(Collection 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

subList

(int fromIndex, int toIndex)

截取部分

list

public static void main(String[] args) {

LinkedList 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 copy = list.subList(0, 3);

System.out.println(list);

System.out.println(copy);

list.clear(); // 将list中元素清空

System.out.println(list.size());

}

3.LinkedList的遍历

public static void main(String[] args) {

LinkedList 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());

// foreach遍历

for (int e:list) {

System.out.print(e + " ");

}

System.out.println();

// 使用迭代器遍历---正向遍历

ListIterator it = list.listIterator();

while(it.hasNext()){

System.out.print(it.next()+ " ");

}

System.out.println();

// 使用反向迭代器---反向遍历

ListIterator rit = list.listIterator(list.size());

while (rit.hasPrevious()){

System.out.print(rit.previous() +" ");

}

System.out.println();

}

三，ArrayList与LinkedList的区别

不同点

ArrayList

LinkedList

存储空间上

物理上一定连续

逻辑上连续，但物理上不一定连续

随机访问

支持

O(1)

不支持：

O(N)

头插

需要搬移元素，效率低

O(N)

只需修改引用的指向，时间复杂度为

O(1)

插入

空间不够时需要扩容

没有容量的概念

应用场景

元素高效存储

+

频繁访问

任意位置插入和删除频繁

完。

相关链接

 您阅读本篇文章共花了：