专栏：数据结构(Java版)
个人主页：手握风云
目录
一、LinkedList的模拟实现
1.1. 头插法
1.2. 尾插法
1.3. 插入中间节点
1.4. 删除某个节点
1.5. 删除所有为key的元素
二、LinkedList的使用
2.1. 什么是LinkedList
2.2. LinkedList的使⽤
三、ArrayList和LinkedList的区别
一、LinkedList的模拟实现
在前几期当中，我们实现的都是单向链表，这次我们要实现的是双向链表。双向链表每个节点包含三个域，分别是val，储存数据；prev储存上一个节点的地址；next，储存下一个节点的地址。（如下图所示）
对于双向链表的实现，我们新建一个MyLinkedList类，新建一个接口IList，在类里面重写IList里面的方法。
public class MyLinkedList implements IList{
static class ListNode{
public int val;
public ListNode prev;
public ListNode head;
public ListNode(int val) {
this.val = val;
}
}
public ListNode head;//链表的头
public ListNode last;//链表的尾
@Override
public void addFirst(int data) {
}
@Override
public void addLast(int data) {
}
@Override
public void addIndex(int index, int data) {
}
@Override
public boolean contains(int key) {
return false;
}
@Override
public void remove(int key) {
}
@Override
public void removeAllKey(int key) {
}
@Override
public int size() {
return 0;
}
@Override
public void display() {
}
@Override
public void clear() {
}
}
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();
}
1.1. 头插法
对于实现尾插的方法其实很简单，把新的节点的next存储下一个节点的地址，同时旧的头节点的prev也要存储新的头节点的地址。
@Override
public void addFirst(int data) {
ListNode node = new ListNode(data);
if(head == null){
head = node;
last = node;
}else{
node.next = head;
head.prev = node;
head = node;
}
}
@Override
public void display() {
ListNode cur = head;
while(cur != null){
System.out.print(cur.val+" ");
cur = cur.next;
}
}public class Main {
public static void main(String[] args) {
MyLinkedList myLinkedList = new MyLinkedList();
myLinkedList.addFirst(50);
myLinkedList.addFirst(40);
myLinkedList.addFirst(30);
myLinkedList.addFirst(20);
myLinkedList.addFirst(10);
myLinkedList.addFirst(5);
myLinkedList.display();
}
}
我们顺带也可以完成对链表长度和是否含有某个元素的实现
@Override
public int size() {
int count = 0;
ListNode cur = head;
while(cur != null){
count++;
cur = cur.next;
}
return count;
}
public class Main {
public static void main(String[] args) {
MyLinkedList myLinkedList = new MyLinkedList();
myLinkedList.addLast(10);
myLinkedList.addLast(20);
myLinkedList.addLast(30);
myLinkedList.addLast(40);
myLinkedList.addLast(50);
myLinkedList.addLast(60);
System.out.println(myLinkedList.size());
}
}@Override
public boolean contains(int key) {
ListNode cur = head;
while(cur != null){
if(cur.val == key){
return true;
}
cur = cur.next;
}
return false;
}1.2. 尾插法
尾插法与头插法极其类似，这里不再过多叙述。
@Override
public void addLast(int data) {
ListNode node = new ListNode(data);
if(head == null){
head = node;
last = node;
}else{
last.next = node;
node.prev = last;
last = node;
}
}public class Main {
public static void main(String[] args) {
MyLinkedList myLinkedList = new MyLinkedList();
myLinkedList.addLast(10);
myLinkedList.addLast(20);
myLinkedList.addLast(30);
myLinkedList.addLast(40);
myLinkedList.addLast(50);
myLinkedList.addLast(60);
myLinkedList.display();
}
}
1.3. 插入中间节点
如图所示，我们需要用到4个引用，大致过程可以通过4行代码来实现。先绑定后面，要注意修改每一个引用的时候，不能因为修改了前面而影响了后面。
node.next = cur;
cur.prev.next = node;
node.prev = cur.prev;
cur.prev = node;@Override
public void addIndex(int index, int data) {
int len = size();
if(index<0 || index>len){
throw new RuntimeException("双向链表位置不合法:"+index);
}
if(index == 0){
addFirst(data);
return;
}
if(index == len){
addLast(data);
}
ListNode node = new ListNode(data);
ListNode cur = findIndex(index);
node.next = cur;
cur.prev.next = node;
node.prev = cur.prev;
cur.prev = node;
}
private ListNode findIndex(int index){
ListNode cur = head;
while(index != 0){
cur = cur.next;
index--;
}
return cur;
}
1.4. 删除某个节点
如果说，我们删除的只是中间的某个节点，我们只需要两行代码就能实现。
cur.prev.next = cur.next;
cur.next.prev = cur.prev;但是我们要删除的是头节点或者尾结点呢？我们可以先让head向前走一步，再把head.prev置为空，同理last节点也可以。
@Override
public void remove(int key) {
ListNode cur = head;
while(cur != null){
if(cur.val == key){
//删除头节点
if(cur == head){
head = head.next;
head.prev = null;
}else{
//删除尾结点
if(cur == last){
last = last.prev;
last.next = null;
}else{
//删除中间节点
cur.prev.next = cur.next;
cur.next.prev = cur.prev;
}
}
return;
}else{
cur = cur.next;
}
}
}这么看我们的代码好像没问题，但我们需要考虑一个问题，如果说链表只有一个节点呢？就会抛出下图这样一个异常，我们只需要把last也手动置为空。
完整代码：
@Override
public void remove(int key) {
ListNode cur = head;
while(cur != null){
if(cur.val == key){
//删除头节点
if(cur == head){
head = head.next;
if(head == null){
last = null;
return;
}
head.prev = null;
}else{
//删除尾结点
if(cur == last){
last = last.prev;
last.next = null;
}else{
//删除中间节点
cur.prev.next = cur.next;
cur.next.prev = cur.prev;
}
}
return;
}else{
cur = cur.next;
}
}
}1.5. 删除所有为key的元素
我们只需要对上一个方法进行一点改动就可以实现。我们让cur只遍历一遍链表，每次cur走完if语句之后直接去指向下一个节点。
@Override
public void removeAllKey(int key) {
ListNode cur = head;
while(cur != null){
if(cur.val == key){
//删除头节点
if(cur == head){
head = head.next;
if(head == null){
last = null;
return;
}
head.prev = null;
}else{
//删除尾结点
if(cur == last){
last = last.prev;
last.next = null;
}else{
//删除中间节点
cur.prev.next = cur.next;
cur.next.prev = cur.prev;
}
}
}
cur = cur.next;
}
}二、LinkedList的使用
2.1. 什么是LinkedList
从上面的图中可以看到LinkedList实现了众多的接口来帮助我们实现各种各样的功能，这里我们主要看List的接口。我们看一下LinkedList里面的源码
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable
2.2. LinkedList的使⽤
import java.util.LinkedList;
public class Main {
public static void main(String[] args) {
LinkedList<Integer> linkedList = new LinkedList<>();
linkedList.addFirst(10);
linkedList.addLast(20);
System.out.println(linkedList);
}
}我们通过LinkedList创建对象的时候，就可以直接调用以上方法。我们看一下addFirst和addLast的源码。
public void addFirst(E e) {
linkFirst(e);
}
public void add(E e) {
checkForComodification();
lastReturned = null;
if (next == null)
linkLast(e);
else
linkBefore(e, next);
nextIndex++;
expectedModCount++;
}我们可以看到，代码的思路与我们上面自己实现的基本一致。我们同样可以初始化一个ArrayList。下面是一些常用方法：
import java.util.LinkedList;
public class Main {
public static void main(String[] args) {
LinkedList<Integer> list1 = new LinkedList<>();
list1.add(1);//表示尾插
list1.add(2);
list1.add(3);
list1.add(4);
list1.add(5);
list1.add(6);
list1.add(3,100);//在下标为3的位置插入100
System.out.println(list1);
LinkedList<Integer> list2 = new LinkedList<>();
list2.add(11);
list2.add(22);
list2.add(33);
list1.addAll(2,list2);
System.out.println(list1);
list1.remove(2);//删除下标为2的元素
list1.removeFirst();//删除头元素
list1.removeLast();//删除尾元素
System.out.println(list1);
System.out.println(list1.get(2));//获取下标为2的元素
list1.set(0,20);
System.out.println(list1);//将下标为0的元素设置为20
}
}三、ArrayList和LinkedList的区别
| 不同点 | ArrayList | LinkedList |
| 存储空间上 | 物理上一定连续 | 逻辑上连续，但物理上不一定连续 |
| 随机访问 | 支持O(1) | 不支持O(n) |
| 头插 | 需要搬移元素，效率低O(n) | 只需要改变指向，时间复杂度O(1) |
| 插入 | 空间不够时需要扩容 | 没有容量的概念 |
