Java LinkedList

链表（Linked list）是一种常见的基础数据结构，是一种线性表，但是并不会按线性的顺序存储数据，而是在每一个节点里存到下一个节点的地址 链表可分为单向链表和双向链表。 一个单向链表包含两个值: 当前节点的值和一个指向下一个节点的链接 一个双向链表有三个整数值: 数值、向后的节点链接、向前的节点链接 Java LinkedList（链表） 类似于 ArrayList，是一种常用的数据容器。 与 ArrayList 相比，LinkedList 的增加和删除对操作效率更高，而查找和修改的操作效率较低

ArrayList与LinkedList的使用挑选

以下情况使用 ArrayList :

• 频繁访问列表中的某一个元素
• 只需要在列表末尾进行添加和删除元素操作

以下情况使用 LinkedList :

• 你需要通过循环迭代来访问列表中的某些元素
• 需要频繁的在列表开头、中间、末尾等位置进行添加和删除元素操作

LinkedList链表储存结构与特点

链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。由一系列结点node(链表中每一个元素称为结点)组成，结点可以在运行时动态生成
链表特点:

• 查询慢 链表中地址不是连续的,每次查询元素都必须从头开始查询
• 增删快 链表结构增删一个元素,对链表的整体结构没有什么影响,所以增删快

每个结点包括两个部分：

• 存储数据元素的数据域
• 存储下一个结点地址的指针域

我们常说的链表结构有单向链表与双向链表

• 单向链表 只有一条链子,不能保证元素的顺序(存储元素和取出元素顺序有可能不一致)

• 双向链表 有两条链子,有一条是专门记录元素的顺序,是一个有序的集合

LinkedList继承与接口关系

• LinkedList 继承了 AbstractSequentialList 类。
• LinkedList 实现了 Queue 接口，可作为队列使用
• LinkedList 实现了 List 接口，可进行列表的相关操作
• LinkedList 实现了 Deque 接口，可作为队列使用
• LinkedList 实现了 Cloneable 接口，可实现克隆
• LinkedList 实现了 java.io.Serializable 接口，即可支持序列化，能通过序列化去传输

LinkedList 类位于 java.util 包中，使用前需要引入它，语法格式如下：

// 引入 LinkedList 类
import java.util.LinkedList; 
LinkedList<E> list = new LinkedList<E>();   // 普通创建方法
或者
LinkedList<E> list = new LinkedList(Collection<? extends E> c); // 使用集合创建链表

常用方法

更多 API 方法可以查看：https://www.runoob.com/manual/jdk11api/java.base/java/util/LinkedList.html

LinkedList实例

创建一个简单的链表实例

import java.util.LinkedList;
public class TestLinkedList {
    public static void main(final String[] args) {
        final LinkedList<String> sites = new LinkedList<String>();
        sites.add("Google");
        sites.add("Apple");
        sites.add("MicroSoft");
        System.out.println(sites);
    }
}
// [Google,Apple,MicroSoft]

更多的情况下我们使用 ArrayList 访问列表中的随机元素更加高效，但以下几种情况 LinkedList 提供了更高效的方法

在列表开头添加元素：

import java.util.LinkedList;

public class TestLinkedList {
    public static void main(String[] args) {
        LinkedList<String> sites = new LinkedList<String>();
        sites.add("Google");
        sites.add("Apple");
        sites.add("MicroSoft");

        sites.addFirst("Wiki");  // 使用 addFirst() 在头部添加元素
        System.out.println(sites); // [Wiki, Google, Apple, MicroSoft]
    }
}

在列表结尾添加元素

import java.util.LinkedList;

public class TestLinkedList {
    public static void main(String[] args) {
        LinkedList<String> sites = new LinkedList<String>();
        sites.add("Google");
        sites.add("Apple");
        sites.add("MicroSoft");

        sites.addLast("Wiki");  // 使用 addLast() 在尾部添加元素
        System.out.println(sites); // [Google, Apple, MicroSoft, Wiki]
    }
}

在列表开头移除元素

import java.util.LinkedList;

public class TestLinkedList {
    public static void main(String[] args) {
        LinkedList<String> sites = new LinkedList<String>();
        sites.add("Google");
        sites.add("Apple");
        sites.add("MicroSoft");

        sites.removeFirst(); // 使用 removeFirst() 移除头部元素
        System.out.println(sites); // [Apple, MicroSoft]
    }
}

在列表结尾移除元素

import java.util.LinkedList;

public class TestLinkedList {
    public static void main(String[] args) {
        LinkedList<String> sites = new LinkedList<String>();
        sites.add("Google");
        sites.add("Apple");
        sites.add("MicroSoft");

        sites.removeLast(); // 使用 removeLast() 移除尾部元素
        System.out.println(sites); // [Google, Apple]
    }
}

获取列表开头的元素

import java.util.LinkedList;

public class TestLinkedList {
    public static void main(String[] args) {
        LinkedList<String> sites = new LinkedList<String>();
        sites.add("Google");
        sites.add("Apple");
        sites.add("MicroSoft");

        // 使用 getFirst() 获取头部元素 
        System.out.println(sites.getFirst()); //Google
    }
}

获取列表结尾的元素：

import java.util.LinkedList;

public class TestLinkedList {
    public static void main(String[] args) {
        LinkedList<String> sites = new LinkedList<String>();
        sites.add("Google");
        sites.add("Apple");
        sites.add("MicroSoft");

        // 使用 getLast() 获取尾部元素
        System.out.println(sites.getLast()); // MicroSoft
    }
}

迭代元素

我们可以使用 for 配合 size() 方法来迭代列表中的元素：

import java.util.LinkedList;

public class TestLinkedList {
    public static void main(String[] args) {
        LinkedList<String> sites = new LinkedList<String>();
        sites.add("Google");
        sites.add("Apple");
        sites.add("MicroSoft");

        for (int size = sites.size(), i = 0; i < size; i++) {
            System.out.println(sites.get(i));
        }

        for (String i : sites) {
            System.out.println(i);
        }
    }
}

/* 
Google
Apple
MicroSoft 
*/

拓展：自己实现一个链表

1. 先建立链表结点以及整个链表的实体类；这里有两个实体类：
   • LinkNode是结点，包括结点的数据域和指针域；
   • LinkList是整个链表，包括头结点以及链表元素个数； ```jsx package com.java.model;

public class LinkNode { // 链表结点的数据域 public Object data; // 链表结点的指针域 public LinkNode next;

public LinkNode() { super(); // TODO Auto-generated constructor stub }

// 构造方法 public LinkNode(Object data, LinkNode next) { super(); this.data = data; this.next = next; }

}

```jsx
package com.java.model;

public class LinkList {
   //链表的头结点
   public LinkNode head;
   //链表的元素个数
   public int size;

   public LinkList() {
       super();
       // TODO Auto-generated constructor stub
   }

   ///构造方法
   public LinkList(LinkNode head, int size) {
       super();
       this.head = head;
       this.size = size;
   }
}

1. 再写链表方法类LinkListDao； ```jsx package com.java.dao;

import com.java.model.LinkList; import com.java.model.LinkNode;

public class LinkListDao { // 初始化链表 public LinkList Init_LinkList() { // 设置头结点的指针域和数据域 LinkNode node = new LinkNode(0, null); LinkList list = new LinkList(node, 0); return list; }

// 指定位置插入 public void Insert_LinkList(LinkList list, int pos, Object data) { // 判断list是否有效 if (list == null) { return; } // 判断data是否有效 if (data == null) { return; } // 判断位置pos是否有效 if (pos < 0 || pos > list.size) { // 在链表的尾部插入 pos = list.size; }

// 第一步，创建新的结点，也就是待插入的结点
LinkNode newNode = new LinkNode(data, null);
// 第二步，找到待插入结点前面一个结点pCurrent，并使其等于list的头结点
LinkNode pCurrent = list.head;
for (int i = 0; i < pos; i++) {
  pCurrent = pCurrent.next;
}
// 第三步，新结点入链表，进行插入操作
newNode.next = pCurrent.next;
pCurrent.next = newNode;
// 第四步，链表的size要加1
list.size++;

}

// 删除指定位置的值 public void RemoveByPos_LinkList(LinkList list, int pos) { if (list == null) { return; } if (pos < 0 || pos >= list.size) { return; } // 第一步，找到待删除结点的前面一个结点pCurrent LinkNode pCurrent = list.head; for (int i = 0; i < pos; i++) { pCurrent = pCurrent.next; } // 第二步，进行删除操作 pCurrent.next = pCurrent.next.next; // 第三步，链表的size要减1 list.size—; }

// 获得链表的长度 public int Size_LinkList(LinkList list) { return list.size; }

// 查找指定元素的位置 public void Find_LinkList(LinkList list, Object data) { // 注意这里要从头结点的下一个结点开始，因为头结点不存放数据信息 LinkNode pCurrent = list.head.next; for (int i = 0; i < list.size; i++) { if (pCurrent.data == data) { System.out.print(i + “,”); } pCurrent = pCurrent.next; } }

// 返回第一个结点元素的值 public Object Front_LinkList(LinkList list) { return list.head.next.data; }

// 打印链表结点 public void Print_LinkList(LinkList list) { if (list == null) { return; } LinkNode pCurrent = list.head.next; for (int i = 0; i < list.size; i++) { System.out.print(pCurrent.data + “,”); pCurrent = pCurrent.next; } }

}

3. 主函数Main；测试各种方法类；
```jsx
package com.java.main;

import com.java.dao.LinkListDao;
import com.java.model.LinkList;

public class LinkListMain {
  public static void main(String[] args) {
    LinkListDao linkListDao = new LinkListDao();
    // 创建链表
    LinkList list = linkListDao.Init_LinkList();

    // 数据插入链表
    linkListDao.Insert_LinkList(list, 0, "A");
    linkListDao.Insert_LinkList(list, 1, "B");
    linkListDao.Insert_LinkList(list, 2, "C");
    linkListDao.Insert_LinkList(list, 3, "D");
    linkListDao.Insert_LinkList(list, 4, "D");

    // 打印链表
    System.out.println("插入数据之后的链表为:");
    linkListDao.Print_LinkList(list);
    System.out.println();

    // 删除指定位置的值
    linkListDao.RemoveByPos_LinkList(list, 2);

    // 打印链表
    System.out.println("删除元素C之后的链表为:");
    linkListDao.Print_LinkList(list);
    System.out.println();

    // 获得链表长度
    System.out.println("链表长度为:");
    System.out.println(linkListDao.Size_LinkList(list));

    // 查找值为3的位置
    System.out.println("值为D的位置为:");
    linkListDao.Find_LinkList(list, "D");
    System.out.println();

    // 返回第一个结点元素的值
    System.out.println("第一个结点元素为:");
    System.out.println(linkListDao.Front_LinkList(list));
  }
}