目录
一. LinkedList 基本介绍
(1)LinkedList (链表) 继承于 List接口, 是Java集合框架的一部分.
(2) LinkedList 用于存放可重复, 有序的元素.
(3) LinkedList 底层使用双向链表来实现.
(4) LinkedList 的特点是 插入/删除 的速度快 (因为可以直接通过下标查找), 查找 元素的速度慢(因为需要先遍历链表找到对应元素).
二. LinkedList 中的法及其应用
通过查看文档我们可以看到, LinkedList 类主要有以上几种方法. 我把其中比较重要的几个方法勾选了出来, 这些我们要重点熟悉掌握. 大家也可以自行翻阅文档进行学习.
首先我们要在list里存放对象. 假设我们要存放Student类型的对象.
首先定义学生类:
public class Student {
private String name;
private int age;
public Student(String name, int age) {
this.name = name;
this.age = age;
}
public String getName() {
return name;
}
public int getAge() {
return age;
}
public void setName(String name) {
this.name = name;
}
public void setAge(int age) {
this.age = age;
}
@Override
public String toString() {
return "Student{" +
"name='" + name + '\'' +
", age=" + age +
'}';
}
@Override
public boolean equals(Object obj) {
if (this == obj) { //1. 如果this和obj指向同一个对象, 则返回true;
return true;
}
if (obj instanceof Student) { //2. 如果this和obj指向不同对象, 而且obj是Student类型的
if (this.age == ((Student) obj).getAge() && this.name == ((Student) obj).getName()) {
return true;
}
return false;
}
return false;
}
}1. 添加元素
(1) add()
add() 方法, 有两个版本: 版本一有一个参数, 版本二有两个参数.
[1] add(E e) 将指定元素添加到末尾
import java.util.LinkedList;
public class demo {
public static void main(String[] args) {
Student s1 = new Student("刘德华",22);
Student s2 = new Student("梁朝伟",24);
Student s3 = new Student("吴彦祖",26);
LinkedList<Student> linkedList = new LinkedList<>();
linkedList.add(s1);
linkedList.add(s2);
linkedList.add(s3);
System.out.println(linkedList);
}
}
[2] add(int index, E element) 将指定元素插入指定位置.
import java.util.LinkedList;
public class demo {
public static void main(String[] args) {
Student s1 = new Student("刘德华",22);
Student s2 = new Student("梁朝伟",24);
Student s3 = new Student("吴彦祖",26);
LinkedList<Student> linkedList = new LinkedList<>();
linkedList.add(s1);
linkedList.add(s2);
linkedList.add(s3);
System.out.println(linkedList);
Student s4 = new Student("Jack",45);
linkedList.add(1,s4);
System.out.println(linkedList);
}
}
(2) addAll()
addAll() 方法的基本作用是将一个列表添加到另一个列表中去. 与add() 类似, addAll() 方法也有两个版本:
[1] addAll(Collection e) 表示将另一列表添加到当前列表之后.
import java.util.LinkedList;
public class demo {
public static void main(String[] args) {
Student s1 = new Student("刘德华",22);
Student s2 = new Student("梁朝伟",24);
Student s3 = new Student("吴彦祖",26);
LinkedList<Student> linkedList = new LinkedList<>();
linkedList.add(s1);
linkedList.add(s2);
linkedList.add(s3);
System.out.println(linkedList); // 打印linkedList
Student s4 = new Student("Jack",45);
Student s5 = new Student("Bob", 55);
Student s6 = new Student("Molly",31);
LinkedList<Student> linkedList1 = new LinkedList<>();
linkedList1.add(s4);
linkedList1.add(s5);
linkedList1.add(s6);
System.out.println(linkedList1); // 打印linkedList1
linkedList.addAll(linkedList1);
System.out.println(linkedList); // 打印合并之后的linkedList
}
}
[2] addAll(intindex, Collection e) 表示在指定位置插入另一列表.
import java.util.LinkedList;
public class demo {
public static void main(String[] args) {
Student s1 = new Student("刘德华",22);
Student s2 = new Student("梁朝伟",24);
Student s3 = new Student("吴彦祖",26);
LinkedList<Student> linkedList = new LinkedList<>();
linkedList.add(s1);
linkedList.add(s2);
linkedList.add(s3);
System.out.println(linkedList);
Student s4 = new Student("Jack",45);
Student s5 = new Student("Bob", 55);
Student s6 = new Student("Molly",31);
LinkedList<Student> linkedList1 = new LinkedList<>();
linkedList1.add(s4);
linkedList1.add(s5);
linkedList1.add(s6);
System.out.println(linkedList1);
linkedList.addAll(1,linkedList1);
System.out.println(linkedList);
}
}
(3) addFirst()
头插. 即在链表的第一个节点之前插入
import java.util.LinkedList;
public class demo {
public static void main(String[] args) {
Student s1 = new Student("刘德华",22);
Student s2 = new Student("梁朝伟",24);
Student s3 = new Student("吴彦祖",26);
LinkedList<Student> linkedList = new LinkedList<>();
linkedList.add(s1);
linkedList.add(s2);
linkedList.add(s3);
System.out.println(linkedList);
Student s4 = new Student("Jack",45);
linkedList.addFirst(s4);
System.out.println(linkedList);
}
}
(4) addLast()
尾插. 即在链表的最后一个节点之后插入
import java.util.LinkedList;
public class demo {
public static void main(String[] args) {
Student s1 = new Student("刘德华",22);
Student s2 = new Student("梁朝伟",24);
Student s3 = new Student("吴彦祖",26);
LinkedList<Student> linkedList = new LinkedList<>();
linkedList.add(s1);
linkedList.add(s2);
linkedList.add(s3);
System.out.println(linkedList);
Student s4 = new Student("Jack",45);
linkedList.addLast(s4);
System.out.println(linkedList);
}
}
2. 删除元素
(1) remove()
remove() 方法, 参数可以传递下标, 也可以传递对象的引用. 作用都是把指定节点删除掉. 代码演示如下:
import java.util.LinkedList;
public class demo {
public static void main(String[] args) {
Student s1 = new Student("刘德华",22);
Student s2 = new Student("梁朝伟",24);
Student s3 = new Student("吴彦祖",26);
LinkedList<Student> linkedList = new LinkedList<>();
linkedList.add(s1);
linkedList.add(s2);
linkedList.add(s3);
System.out.println(linkedList);
linkedList.remove(0); // 传递下标删除元素
System.out.println(linkedList);
linkedList.remove(s2); // 传递对象删除元素
System.out.println(linkedList);
}
}
(2) removeAll()
与add()和addAll()的关系类似, remove()方法是删除单个元素, removeAll()方法是从一个列表里删除另一个列表中的所有元素.
因为我们在Student里重写了equals()方法, 所以只要两个对象的name和age属性一样, 那么就认为这两个对象是相同的.
import java.util.LinkedList;
public class demo {
public static void main(String[] args) {
Student s1 = new Student("刘德华",22);
Student s2 = new Student("梁朝伟",24);
Student s3 = new Student("吴彦祖",26);
LinkedList<Student> linkedList = new LinkedList<>();
linkedList.add(s1);
linkedList.add(s2);
linkedList.add(s3);
System.out.println(linkedList);
LinkedList<Student> linkedList1 = new LinkedList<>();
linkedList1.add(s1);
linkedList1.add(s2);
System.out.println(linkedList1);
linkedList.removeAll(linkedList1);
System.out.println(linkedList);
}
}
(3) removeFirst()
删除并返回链表第一个元素.
import java.util.LinkedList;
public class demo {
public static void main(String[] args) {
Student s1 = new Student("刘德华",22);
Student s2 = new Student("梁朝伟",24);
Student s3 = new Student("吴彦祖",26);
LinkedList<Student> linkedList = new LinkedList<>();
linkedList.add(s1);
linkedList.add(s2);
linkedList.add(s3);
System.out.println(linkedList);
linkedList.removeFirst();
System.out.println(linkedList);
}
}
注意, 上面代码中的 removeFirst() 有返回值, 但是我们没有接收.
(4) removeLast()
删除并返回链表最后一个元素.
import java.util.LinkedList;
public class demo {
public static void main(String[] args) {
Student s1 = new Student("刘德华",22);
Student s2 = new Student("梁朝伟",24);
Student s3 = new Student("吴彦祖",26);
LinkedList<Student> linkedList = new LinkedList<>();
linkedList.add(s1);
linkedList.add(s2);
linkedList.add(s3);
System.out.println(linkedList);
linkedList.removeLast();
System.out.println(linkedList);
}
} 
3. 遍历元素
(1) for 循环遍历
import java.util.LinkedList;
public class demo {
public static void main(String[] args) {
Student s1 = new Student("刘德华",22);
Student s2 = new Student("梁朝伟",24);
Student s3 = new Student("吴彦祖",26);
LinkedList<Student> linkedList = new LinkedList<>();
linkedList.add(s1);
linkedList.add(s2);
linkedList.add(s3);
for (int i = 0; i < linkedList.size(); i++) {
System.out.println(linkedList.get(i));
}
}
}
(2) for - each 遍历
import java.util.LinkedList;
public class demo {
public static void main(String[] args) {
Student s1 = new Student("刘德华",22);
Student s2 = new Student("梁朝伟",24);
Student s3 = new Student("吴彦祖",26);
LinkedList<Student> linkedList = new LinkedList<>();
linkedList.add(s1);
linkedList.add(s2);
linkedList.add(s3);
for (Student stu: linkedList) {
System.out.println(stu);
}
}
}
(3) 迭代器遍历
import java.util.Iterator;
import java.util.LinkedList;
public class demo {
public static void main(String[] args) {
Student s1 = new Student("刘德华",22);
Student s2 = new Student("梁朝伟",24);
Student s3 = new Student("吴彦祖",26);
LinkedList<Student> linkedList = new LinkedList<>();
linkedList.add(s1);
linkedList.add(s2);
linkedList.add(s3);
Iterator<Student> iterator = linkedList.iterator();
while (iterator.hasNext()) {
System.out.println(iterator.next());
}
}
}
(4) 列表迭代器遍历
- 正序遍历:
import java.util.Iterator;
import java.util.LinkedList;
import java.util.ListIterator;
public class demo {
public static void main(String[] args) {
Student s1 = new Student("刘德华",22);
Student s2 = new Student("梁朝伟",24);
Student s3 = new Student("吴彦祖",26);
LinkedList<Student> linkedList = new LinkedList<>();
linkedList.add(s1);
linkedList.add(s2);
linkedList.add(s3);
ListIterator<Student> iterator = linkedList.listIterator();
while (iterator.hasNext()) {
System.out.println(iterator.next());
}
}
}
- 逆序遍历:
import java.util.Iterator;
import java.util.LinkedList;
import java.util.ListIterator;
public class demo {
public static void main(String[] args) {
Student s1 = new Student("刘德华",22);
Student s2 = new Student("梁朝伟",24);
Student s3 = new Student("吴彦祖",26);
LinkedList<Student> linkedList = new LinkedList<>();
linkedList.add(s1);
linkedList.add(s2);
linkedList.add(s3);
ListIterator<Student> iterator = linkedList.listIterator(linkedList.size()); // 相当于把迭代器插入到 size() 位置的前面. 从这里开始遍历
while (iterator.hasPrevious()) {
System.out.println(iterator.previous());
}
}
}[注]: 这里我们需要注意一点: 给 listIterator() 传参数 就表示将迭代器插入到index位置的前面.
所以这里给listIterator() 传了一个arrayList.size(), 就相当于把迭代器插入到了 size() 位置的前面
4. 判断
(1) cotains()
public class demo {
public static void main(String[] args) {
Student s1 = new Student("刘德华",22);
Student s2 = new Student("梁朝伟",24);
Student s3 = new Student("吴彦祖",26);
LinkedList<Student> linkedList = new LinkedList<>();
linkedList.add(s1);
linkedList.add(s2);
linkedList.add(s3);
System.out.println(linkedList.contains(new Student("吴彦祖", 26)));
System.out.println(linkedList.contains(new Student("周润发", 50)));
}
}
(2) containsAll()
public class demo1 {
public static void main(String[] args) {
Student s1 = new Student("刘德华",22);
Student s2 = new Student("梁朝伟",24);
Student s3 = new Student("吴彦祖",26);
LinkedList<Student> linkedList = new LinkedList<>();
linkedList.add(s1);
linkedList.add(s2);
linkedList.add(s3);
LinkedList<Student> linkedList1= new LinkedList<>();
linkedList1.add(s1);
linkedList1.add(s2);
System.out.println(linkedList.containsAll(linkedList1));
}
}
(3) isEmpty()
判断当前顺序列表是否为空.
public class demo {
public static void main(String[] args) {
Student s1 = new Student("刘德华",22);
Student s2 = new Student("梁朝伟",24);
Student s3 = new Student("吴彦祖",26);
LinkedList<Student> linkedList = new LinkedList<>();
linkedList.add(s1);
linkedList.add(s2);
linkedList.add(s3);
System.out.println(linkedList.isEmpty());
linkedList.clear();
System.out.println(linkedList.isEmpty());
}
}
三. 模拟实现 LinkedList
我们前面说, LinkedList 是基于双向链表实现的. 那么单向链表可不可以实现LinkedList呢? --> 同样是可以的. 我们分别用 单向链表 和 双向链表 实现一次LInkedList~
为了实现起来简单, 我们自己实现LinkedList只能存放 int 类型的元素.
1. 使用单向链表模拟实现
- 模拟链表代码:
public class MyLinkedList {
class ListNode {
public int val; //值域
public ListNode next; //指针域 (初值为null)
public ListNode(int val) {
this.val = val;
}
}
ListNode head; //头指针
public int size() {
ListNode p = head;
int count = 0;
while (p != null) {
count ++;
p = p.next;
}
return count;
}
public void addLast(int val) { //模拟实现addLast (尾插)
ListNode newNode = new ListNode(val);
if (head == null) {
head = newNode;
} else{
ListNode p = head;
while (p.next != null) { //找尾结点
p = p.next;
}
p.next = newNode;
}
}
public boolean addFirst(int val) { //模拟实现addFirst (头插)
if (head == null) {
return false;
}
ListNode newNode = new ListNode(val);
newNode.next = head;
head = newNode;
return true;
}
public boolean addIndex(int index, int val) { //模拟实现addIndex (在指定位置插入)
if (index < 0 || index > size()) {
System.out.println("输入的下标有误, 请检查");
return false;
}
if (head == null) {
return false;
}
ListNode newNode = new ListNode(val);
// 找到index位置的前一个
ListNode TargetPreviousNode = head;
int stepCount = index-1;
while (stepCount !=0) {
TargetPreviousNode = TargetPreviousNode.next;
stepCount--;
}
ListNode TargetNode = TargetPreviousNode.next;
//添加节点
TargetPreviousNode.next = newNode;
newNode.next = TargetNode;
return true;
}
public boolean removeLast() { //模拟实现removeLast (尾删)
// 判空
if (head == null) {
return false;
}
// 找到尾结点的前一个节点
ListNode p = head;
while (p.next.next != null) {
p = p.next;
}
p.next = null; // 删除尾结点
return true;
}
public boolean removeFirst() { //模拟实现removeLast (头删)
//判空
if (head == null) {
return false;
}
//
ListNode p = head.next; //p指向头结点的下一个结点.
head.next = null;
head = p;
return true;
}
public boolean removeIndex(int index) { //模拟实现removeIndex (删除指定位置的元素)
if (head == null) {
return false;
}
ListNode TargetPreviousNode = head;
int stepCount = index-1;
while (stepCount != 0) { //找到目标节点的前一个节点
TargetPreviousNode = TargetPreviousNode.next;
}
ListNode TargetNode = TargetPreviousNode.next;
// 删除目标节点
TargetPreviousNode.next = TargetNode.next;
TargetNode.next = null; // 给要删除节点的next域置空.
return true;
}
public boolean removeKey(int data) { //模拟实现removeKey (删除指定定值的元素)
if (head == null) {
return false;
}
int flag = 0;
ListNode TargetPreviousNode = head;
while (TargetPreviousNode.next != null) {
if (TargetPreviousNode.next.val == data) { //定位要删除节点的前一个节点
ListNode TargetNode = TargetPreviousNode.next;
TargetPreviousNode.next = TargetNode.next;
TargetNode.next = null;
flag = 1;
}
TargetPreviousNode = TargetPreviousNode.next;
if (TargetPreviousNode != null) {
continue;
} else {
break;
}
}
if (flag == 1) { //删除成功
return true;
}
return false; //没有 val == data 的结点
}
public boolean contains(int val) { //模拟实现contains (是否包含某一元素)
ListNode p = head;
while (p != null) {
if (p.val == val) {
return true;
}
p = p.next;
}
return false;
}
public boolean isEmpty() { //判断当前链表是否为空
if(head == null) {
return true;
}
return false;
}
public void clear() { //清空链表
head = null;
}
@Override
public String toString() {
String str = "";
ListNode p = head;
while(p != null) {
if (p == head){
str += "[";
str += head.val;
str += ",";
p = p.next;
continue;
}
if (p.next == null) {
str += p.val;
str += "]";
p = p.next;
continue;
}
str += p.val;
str += ",";
p = p.next;
}
return str;
}
}- 测试函数代码:
public class test {
public static void main(String[] args) {
MyLinkedList myLinkedList = new MyLinkedList();
myLinkedList.addLast(1);
myLinkedList.addLast(2);
myLinkedList.addLast(3);
myLinkedList.addLast(4);
myLinkedList.addLast(5);
myLinkedList.addLast(3);
myLinkedList.addLast(3);
System.out.println(myLinkedList);
myLinkedList.addFirst(99);
System.out.println(myLinkedList);
myLinkedList.addIndex(2,88);
System.out.println(myLinkedList);
myLinkedList.removeLast();
System.out.println(myLinkedList);
myLinkedList.removeFirst();
System.out.println(myLinkedList);
myLinkedList.removeIndex(1);
System.out.println(myLinkedList);
myLinkedList.removeKey(3);
System.out.println(myLinkedList);
System.out.println(myLinkedList.contains(5));
System.out.println(myLinkedList.isEmpty());
myLinkedList.clear();
System.out.println(myLinkedList.isEmpty());
}
}
通过运行结果我们可以看到, 我们用单链表模拟实现的LInkedList是没有任何问题的.
2. 使用双向链表模拟实现
- 模拟链表代码:
public class MyTwoWayLinkedList {
class ListNode {
public int val;
public ListNode next; //next域, 存放后一个节点的地址
public ListNode prev; //prev域, 存放前一个节点的地址
public ListNode(int val) {
this.val = val;
}
}
ListNode head; //头指针
ListNode rear; //尾指针
public void addLast(int val) { //尾插
ListNode newNode = new ListNode(val);
if (head == null && rear == null) {
head = rear = newNode;
}
rear.next = newNode;
newNode.prev = rear;
rear = newNode;
}
public void addFirst(int val) { //头插
ListNode newNode = new ListNode(val);
if (head == null && rear == null) {
head = rear = newNode;
return;
}
newNode.next = head;
head.prev = newNode;
head = newNode;
}
public void addIndex(int index, int val) { //插入到指定位置
ListNode newNode = new ListNode(val);
if (head == null && rear == null && index == 0) {
head = rear = newNode;
return;
}
ListNode TargetNode = head;
int stepCount = index;
while (stepCount != 0) {
TargetNode = TargetNode.next;
stepCount--;
}
newNode.next = TargetNode;
newNode.prev = TargetNode.prev;
TargetNode.prev.next = newNode;
TargetNode.prev = newNode;
}
public void removeLast() { //尾删
ListNode p = rear.prev;
rear.prev.next = null;
rear.prev = null;
rear = p;
}
public void removeFirst() { //头删
ListNode p = head.next;
head.next.prev = null;
head.next = null;
head = p;
}
public void removeIndex(int index) { //删除指定位置的元素
ListNode TargetNode = head;
int stepCount = index;
while(stepCount != 0) {
TargetNode = TargetNode.next;
stepCount--;
}
TargetNode.next.prev = TargetNode.prev;
TargetNode.prev.next = TargetNode.next;
TargetNode.next = null;
TargetNode.prev = null;
}
public boolean removeKey(int data) { //删除指定值的元素
ListNode TargetNode = head;
int flag = 0;
while (TargetNode != null) {
if (TargetNode.val == data) {
if (TargetNode == head) {
removeFirst();
flag = 1;
TargetNode = TargetNode.next;
continue;
}
if (TargetNode == rear) {
removeLast();
flag = 1;
TargetNode = TargetNode.next;
continue;
}
ListNode TargetNextNode =TargetNode.next;
TargetNode.next.prev = TargetNode.prev;
TargetNode.prev.next = TargetNode.next;
TargetNode = TargetNextNode;
flag = 1;
}
TargetNode = TargetNode.next;
}
if (flag == 1) { //删除成功
return true;
}else {
System.out.println("不存在该值");
return false;
}
}
public boolean contains(int val) {
ListNode p = head;
while (p != null) {
if (p.val == val) {
return true;
}
p = p.next;
}
return false;
};
public boolean isEmpty() {
if (head == null && rear == null) {
return true;
}
return false;
};
public void clear() {
head = rear = null;
};
@Override
public String toString() {
String str = "";
ListNode p = head;
while(p != null) {
if (p == head){
str += "[";
str += head.val;
str += ",";
p = p.next;
continue;
}
if (p == rear) {
str += rear.val;
str += "]";
p = p.next;
continue;
}
str += p.val;
str += ",";
p = p.next;
}
return str;
}
}
- 测试函数代码:
public class test {
public static void main(String[] args) {
MyTwoWayLinkedList myTwoWayLinkedList = new MyTwoWayLinkedList();
myTwoWayLinkedList.addLast(1);
myTwoWayLinkedList.addLast(2);
myTwoWayLinkedList.addLast(3);
myTwoWayLinkedList.addLast(4);
myTwoWayLinkedList.addLast(5);
myTwoWayLinkedList.addLast(3);
myTwoWayLinkedList.addLast(3);
System.out.println(myTwoWayLinkedList);
myTwoWayLinkedList.addFirst(99);
System.out.println(myTwoWayLinkedList);
myTwoWayLinkedList.addIndex(1,88);
System.out.println(myTwoWayLinkedList);
myTwoWayLinkedList.removeLast();
System.out.println(myTwoWayLinkedList);
myTwoWayLinkedList.removeFirst();
System.out.println(myTwoWayLinkedList);
myTwoWayLinkedList.removeIndex(1);
System.out.println(myTwoWayLinkedList);
myTwoWayLinkedList.removeKey(3);
System.out.println(myTwoWayLinkedList);
System.out.println(myTwoWayLinkedList.contains(88));
System.out.println(myTwoWayLinkedList.isEmpty());
myTwoWayLinkedList.clear();
System.out.println(myTwoWayLinkedList.isEmpty());
}
}