LinkedList类 (链表)
目录
一. LinkedList 基本介绍
二. LinkedList 中的法及其应用
1. 添加元素
(1) add()
(2) addAll()
(3) addFirst()
(4) addLast()
2. 删除元素
(1) remove()
(2) removeAll()
(3) removeFirst()
(4) removeLast()
3. 遍历元素
(1) for 循环遍历
(2) for - each 遍历
(3) 迭代器遍历
(4) 列表迭代器遍历
4. 判断
(1) cotains()
(2) containsAll()
(3) isEmpty()
三. 模拟实现 LinkedList
1. 使用单向链表模拟实现
2. 使用双向链表模拟实现
一. 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;}@Overridepublic String toString() {return "Student{" +"name='" + name + '\'' +", age=" + age +'}';}@Overridepublic 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); // 打印linkedListStudent 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); // 打印linkedList1linkedList.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;}@Overridepublic 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;};@Overridepublic 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());}
}