数据结构(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;//链表的尾 @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的区别