文章目录

• 模拟实现LinkedList
• LinkedList的简单使用
• • LinkedList的一些方法
  • LinkedList的遍历
• 简单对比一下LinkedList和ArrayList

模拟实现LinkedList

在上一篇的博客中，我们讲解了链表的基础知识，并且模拟实现了一个无头单向不循环链表，链表的基础知识讲解，大家有兴趣可以去看一下。Java给我们提供的链表其实是一个双向的链表，那今天我们就完善一下我们的LinkedList的模拟实现。
双向链表的每个节点需要有一个前驱：用来访问前一个结点，和一个后继：用来访问后一个结点，还需要记录第一个结点head，和最后一一个结点last。

public class MyLinkedList2 {static class LinkNode {public int val;//用于储存数据public LinkNode next;//用于找到下一个结点public LinkNode prev;//找到前一个节点public LinkNode(int val) {this.val = val;}}public LinkNode head;//记录第一个节点public LinkNode last;//记录最后一个节点}

有一些方法是不需要进行更改的我就不在进行讲解了，想了解可以看上一篇文章。这里我们只讲解一些需要用到prev的方法，例如头插法：

 public void addFirst(int data){LinkNode newNode = new LinkNode(data);if(head == null) {head = newNode;last = newNode;}else {newNode.next = head;head.prev = newNode;head = newNode;}}

这样就完成了我们的头插法。

尾插法

 public void addLast(int data){LinkNode newNode = new LinkNode(data);if(head == null) {head = newNode;last = newNode;}else {last.next = newNode;newNode.prev = last;last = newNode;}}

在双向链表中尾插法的时间复杂度变为了O(1)，不需要在遍历链表找到最后一个元素进行尾插，我们直接找到记录最后一个节点的last节点就可以进行尾插了。

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

    public void addIndex(int index,int data){try {checkIndex(index);} catch (ListIndexException ex) {ex.printStackTrace();}if(index == 0) {addFirst(data);return ;}if(index == size()) {addLast(data);return ;}LinkNode tmp = FindIndexNode(index);//直接找到该位置的元素就可以不需要找到前一个元素LinkNode newNode = new LinkNode(data);newNode.next = tmp;newNode.prev = tmp.prev;tmp.prev.next = newNode;tmp.prev = newNode;}private LinkNode FindIndexNode(int index) {//找到index位置的结点LinkNode cur = head;while (index != 0) {cur = cur.next;index--;}return cur;}private void checkIndex(int index) throws ListIndexException{if(index < 0 || index > size()) {throw new ListIndexException("插入下标错误");}}

在任意位置插入元素，也不需要向单向链表一样找到要插入位置的前一个节点，我们直接找到要插入位置的节点通过prev就可以访问前一个结点。

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

 public void remove(int key){LinkNode cur = head;while(cur != null) {if(cur.val == key) {//如果要删除的为头节点if(cur == head) {head = head.next;//是否只有一个节点if(head != null) {head.prev = null;}}else {cur.prev.next = cur.next;//判断是否为尾节点if(cur.next != null) {cur.next.prev = cur.prev;}else {last = last.prev;}}return ;}cur = cur.next;}}

删除所有值为key的节点

    public void removeAllKey(int key){LinkNode cur = head;while(cur != null) {if(cur.val == key) {//如果要删除的为头节点if(cur == head) {head = head.next;//是否只有一个节点if(head != null) {head.prev = null;}}else {cur.prev.next = cur.next;//判断是否为尾节点if(cur.next != null) {cur.next.prev = cur.prev;}else {last = last.prev;}}//return ; - 去掉return就实现了}cur = cur.next;}}

这两个方法在双向链表中逻辑是一样的，我们不需要像单向链表一样找到需要删除结点的前一个结点，因为我们有prev可以访问到前一个结点，我们只需要对删除结点是否是头尾进行判断就可以了。

上面图画的是最复杂的情况，如果为头节点和尾结点，将head或者last进行一些改变就可以了，这里就不在画图讲解了。

清空链表

 public void clear() {LinkNode cur = head;while (cur != null) {LinkNode curNext = cur.next;cur.next = null;cur.prev = null;cur = curNext;}head = null;last = null;}

与单向链表相比我们就不能那么暴力了，当然我们也可以将head和last都置为空，但还是太过暴力，我们还是遍历链表将所有结点的next和prev都置为null，这样我们就完善了LinkedList的实现。

LinkedList的简单使用

LinkedList的一些方法

public static void main(String[] args) {LinkedList list = new LinkedList<>();list.add(1);list.add(2);list.add(3);for(Integer num : list) {System.out.print(num + " ");}}

我们创建一个LinkedList的对象调用他的add方法添加一些结点，并且通过foreach的形式遍历链表，这样我们就打印出了链表中的内容，当然我们还可以使用其他的方法对链表进行一些操作，大家可以自己尝试一下。

LinkedList的遍历

1、foreach遍历

 public static void main(String[] args) {LinkedList list = new LinkedList<>();list.add(1);list.add(2);list.add(3);for(Integer num : list) {System.out.print(num + " ");}System.out.println();}

2、迭代器正向遍历

 public static void main(String[] args) {LinkedList list = new LinkedList<>();list.add(1);list.add(2);list.add(3);ListIterator it = list.listIterator();while(it.hasNext()) {System.out.print(it.next() + " ");}System.out.println();}

3、迭代器反向遍历

 public static void main(String[] args) {LinkedList list = new LinkedList<>();list.add(1);list.add(2);list.add(3);ListIterator it2 = list.listIterator(list.size());while(it2.hasPrevious()) {System.out.print(it2.previous() + " ");}System.out.println();}

通过这三种方法我们就可以对LinkedList进行遍历。

简单对比一下LinkedList和ArrayList

学完了这两种数据结构之后，这两种数据结构的使用场景是怎样的呢？二者有什么区别呢？我们来简单总结一下。

所以当我们的业务需求为：需要频繁访问数据时，我们可以用ArrayList顺序表来处理数据，当需求为：频繁的插入删除数据时，我们可以使用LinkedList链表来处理数据。