目录
前言：
由于顺序表底层是一段连续空间，当在ArrayList任意位置插入或者删除元素时，就需要将后序元素整体往前或者往后搬移，时间复杂度为O(n)，效率比较低，因此ArrayList不适合做任意位置插入和删除比较多的场景。因此：java 集合中又引入了LinkedList，即链表结构。
1.链表的概念
链表是一种物理存储结构上非连续存储结构，数据元素的逻辑顺序是通过链表中的引用链接次序实现的 。（物理上是非连续的，逻辑上是连续的）
注意：
1.链式结构在逻辑上是连续的，在物理上不一定是连续的
2.现实中的节点一般都是从堆上申请出来的
3.从堆上申请的空间，是按照一定的策划来分配的，两次申请的空间可能连续，也可能不连续
2.链表的结构
链表有2的3次方种结构：
总的可以分为三类：带头的和不带头的，单向的和双向的，循环和不循环的
2.1带头的和不带头的
上面是单向不循环的带头和不带头的两个链表
注意：
1.带头链表的第一个节点叫做哨兵位，这个节点不存储有效内容
2.每一个节点的next引用指向下一个节点
2.2单向和双向
2.3循环和非循环
虽然总的链表有8种结构，但需要重点掌握的只有两种：
1.无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。
2.无头双向链表：在Java的集合框架库中LinkedList底层实现就是无头双向循环链表。
3.链表的实现
3.1双向不带头不循环链表：
IList：
package OneList;
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 clear();
//打印链表
public void display();
}
方法的实现：
package OneList;
public class MyList implements IList{
static class Node{
Node prv;
Node next;
int x;
public Node(int x) {
this.x = x;
}
}
private int size=0;
private Node head=null;
private Node tail=null;
@Override
public void addFirst(int data) {
Node node=new Node(data);
if (head==null){
head=node;
tail=node;
}else {
node.next=head;
head.prv=node;
head=node;
}
size++;
}
@Override
public void addLast(int data) {
Node node=new Node(data);
if (head==null){
head=node;
tail=node;
}else {
node.prv=tail;
tail.next=node;
tail=node;
}
size++;
}
@Override
public void addIndex(int index, int data) {
Node node=new Node(data);
if (index<0||index>size){
return ;
}
if (index==0){
addFirst(data);
}
else if (index==size){
addLast(data);
}else {
Node cur=head;
while (index>1){
cur=cur.next;
index--;
}
Node t=cur.next;
node.next=t;
t.prv=node;
cur.next=node;
node.prv=cur;
size++;
}
}
@Override
public boolean contains(int key) {
if (head==null){
return false;
}
Node cur=head;
while (cur!=null){
if(cur.x==key){
return true;
}
cur=cur.next;
}
return false;
}
@Override
public void remove(int key) {
if (head==null){
return;
}
if (head.x==key){
head=head.next;
head.prv=null;
size--;
}
Node cur=head;
while (cur.next!=null){
if(cur.x==key){
cur.prv.next=cur.next;
cur.next.prv=cur.prv;
size--;
return;
}
cur=cur.next;
}
if (cur.x==key){
tail=tail.prv;
tail.next=null;
size--;
}
}
@Override
public void removeAllKey(int key) {
if (head==null){
return;
}
Node cur=head;
while (cur!=null){
if(cur.x==key&&cur==head){
head=head.next;
cur=cur.next;
head.prv=null;
size--;
} else if (cur.x==key&&cur==tail) {
tail=tail.prv;
tail.next=null;
size--;
}else if (cur.x==key){
cur.prv.next=cur.next;
cur.next.prv=cur.prv;
cur=cur.next;
size--;
}else {
cur=cur.next;
}
}
}
@Override
public int size() {
return size;
}
@Override
public void clear() {
Node cur=head;
Node next=cur.next;
while (next!=null){
cur=null;
cur=next;
next=next.next;
}
cur=null;
head=null;
tail=null;
}
@Override
public void display() {
if (head==null){
return;
}
Node cur=head;
while (cur!=null){
System.out.print(cur.x+" ");
cur=cur.next;
}
System.out.println();
}
}
3.2单向不带头不循环链表：
IList：
package List;
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();
}
MyList：
package List;
import java.awt.*;
public class MyList implements IList{
static class Node{
int val;
Node next;
public Node(int val) {
this.val = val;
}
}
private int size=0;
private Node head=null;
@Override
public void addFirst(int data) {
Node node=new Node(data);
if (head==null){
head=node;
}else {
node.next=head;
head=node;
}
size++;
}
@Override
public void addLast(int data) {
Node node=new Node(data);
if (head==null){
head=node;
}else {
Node cur=head;
while (cur.next!=null){
cur=cur.next;
}
cur.next=node;
}
size++;
}
@Override
public void addIndex(int index, int data) {
if (index<0||index>size){
return;
}
Node node=new Node(data);
if (index==0){
addFirst(data);
}
else if (index==size){
addLast(data);
}else {
Node cur=head;
while (index>1){
cur=cur.next;
index--;
}
node.next=cur.next;
cur.next=node;
size++;
}
}
@Override
public boolean contains(int key) {
if (head==null){
return false;
}
Node cur=head;
while (cur!=null){
if (cur.val==key){
return true;
}
cur=cur.next;
}
return false;
}
@Override
public void remove(int key) {
if (head == null) {
return;
}
Node cur = head;
if (head.val == key) {
head = head.next;
size--;
return;
}
while (cur.next != null) {
if (cur.next.val == key) {
cur.next = cur.next.next;
size--;
return;
}
cur = cur.next;
}
if (cur.val==key){
cur=null;
size--;
}
}
@Override
public void removeAllKey(int key) {
if (head==null){
return;
}
while(head.val==key){
head=head.next;
size--;
}
Node cur=head;
Node next=head.next;
while (next.next!=null){
if (next.val==key){
cur.next=next.next;
next=next.next;
size--;
}else {
next=next.next;
cur=cur.next;
}
}
if (next.val==key){
cur.next=null;
size--;
}
}
@Override
public int size() {
return size;
}
@Override
public void display() {
Node cur=head;
while (cur!=null){
System.out.print(cur.val+" ");
cur=cur.next;
}
System.out.println();
}
@Override
public void clear() {
Node cur=head;
Node next=cur.next;
while (next!=null){
cur=null;
cur=next;
next=next.next;
}
cur=null;
head=null;
}
}
4.LinkedList的使用
4.1什么是LinkedList
LinkedList的底层是双向链表结构，由于链表没有将元素存储在连续的空间中，元素存储在单独的节点中，然后通过引用将节点连接起来了，因此在在任意位置插入或者删除元素时，不需要搬移元素，效率比较高。
在集合框架中，LinkedList也实现了List接口，具体如下：
说明：
1. LinkedList实现了List接口
2. LinkedList的底层使用了双向链表
3. LinkedList没有实现RandomAccess接口，因此LinkedList不支持随机访问
4. LinkedList的任意位置插入和删除元素时效率比较高，时间复杂度为O(1)
5. LinkedList比较适合任意位置插入的场景
4.2LinkedList的使用
构造方法：
| LinkedList() | 无参构造 |
| public LinkedList(Collection c) | 使用其他集合容器中元素构造List |
public static void main(String[] args) {
// 构造一个空的LinkedList
List<Integer> list1 = new LinkedList<>();
List<String> list2 = new java.util.ArrayList<>();
list2.add("JavaSE");
list2.add("JavaWeb");
list2.add("JavaEE");
// 使用ArrayList构造LinkedList
List<String> list3 = new LinkedList<>(list2);
}LinkedList的其他常用方法：
| boolean add(E e) | 尾插 e |
| void add(int index, E element) | 将 e 插入到 index 位置 |
| boolean addAll(Collection c) | 尾插 c 中的元素 |
| E remove(int index) | 删除 index 位置元素 |
| boolean remove(Object o) | 删除遇到的第一个 o |
| E get(int index) | 获取下标 index 位置元素 |
| E set(int index, E element) | 将下标 index 位置元素设置为 element |
| void clear() | 清空 |
| boolean contains(Object o) | 判断 o 是否在线性表中 |
| int indexOf(Object o) | 返回第一个 o 所在下标 |
| int lastIndexOf(Object o) | 返回最后一个 o 的下标 |
| List subList(int fromIndex, int toIndex) | 截取部分 list |
方法练习使用：
package Test;
import java.util.LinkedList;
public class Test {
public static void main(String[] args) {
LinkedList<Integer>list=new LinkedList<>();
//尾插
list.add(1);
list.add(2);
list.add(3);
list.add(4);
list.add(5);
System.out.println(list);
//指定位置插入
list.add(0,0);
System.out.println(list);
list.add(list.size(), 6);
System.out.println(list);
list.add(5,6);
System.out.println(list);
//头插
list.addFirst(-1);
System.out.println(list);
//尾插
list.addLast(100);
System.out.println(list);
System.out.println("========================================");
//判断元素是否存在
System.out.println(list.contains(1));
//获取下标元素
System.out.println(list.get(1));
//获取第一个元素
System.out.println(list.getFirst());
//获取最后一个元素
System.out.println(list.getLast());
//修改指定位置的元素
list.set(4,99999);
System.out.println(list);
//返回第一次出现元素的下标
System.out.println(list.indexOf(100));
//返回最后一次出现元素的下标
System.out.println(list.lastIndexOf(2));
//截取指定区间的元素（左闭右开）
System.out.println(list.subList(1, 4));
}
}
5.LinkedList的遍历
5.1foreach遍历
for (int x:list) {
System.out.print(x+" ");
}5.2使用迭代器遍历---正向遍历
ListIterator<Integer>lit= list.listIterator();
while (lit.hasNext()){
System.out.print(lit.next()+" ");
}5.3使用迭代器遍历---反向遍历
ListIterator<Integer>it= list.listIterator();
while (it.hasPrevious()){
System.out.print(it.previous()+" ");
}