数据结构(Java版)第九期：LinkedList与链表

专栏：数据结构(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;//链表的尾@Overridepublic void addFirst(int data) {}@Overridepublic void addLast(int data) {}@Overridepublic void addIndex(int index, int data) {}@Overridepublic boolean contains(int key) {return false;}@Overridepublic void remove(int key) {}@Overridepublic void removeAllKey(int key) {}@Overridepublic int size() {return 0;}@Overridepublic void display() {}@Overridepublic 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也要存储新的头节点的地址。

@Overridepublic 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;}}@Overridepublic 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();}
}

    我们顺带也可以完成对链表长度和是否含有某个元素的实现

@Overridepublic 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());}
}

@Overridepublic boolean contains(int key) {ListNode cur = head;while(cur != null){if(cur.val == key){return true;}cur = cur.next;}return false;}

1.2. 尾插法

      尾插法与头插法极其类似，这里不再过多叙述。

@Overridepublic 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;

@Overridepublic 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节点也可以。

@Overridepublic 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也手动置为空。

完整代码：

@Overridepublic 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语句之后直接去指向下一个节点。

@Overridepublic 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);elselinkBefore(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的位置插入100System.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)
插入	空间不够时需要扩容	没有容量的概念