目录
引言
①链表也是一种线性表，那我们既然已经有了顺序表这种数据结构了，又发明链表干嘛呢？
首先，我们知道顺序表根本上讲就是一个数组，那么我们回顾一下顺序表的插入或删除，需要先遍历一遍数组，找到插入或删除的位置，然后进行插删操作，之后必须调整这之后所有元素的位置，这样下来时间复杂度为O（），效率并不是很可观。
②那么，我们想想导致这一原因的因素是什么呢？
就是因为它是数组，它的内存空间物理上是连续的，所以我们每次增删数据，都必须考虑该位置后的元素的位置是否要做出相应的改变。所以，如果我们可以构造一个物理空间上不连续，但它们都具有某种特定关系的线性表不就可以解决这个效率问题了吗，于是有了链表。
链表的定义：链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的引用（也说指针）链接次序实现的。
由于实际上的链表种类较多，根据带头和不带头，单向和双向，循环与非循环分类，可以分成八种，但本文篇幅有限，就介绍不带头单向非循环，不带头双向循环。
一、单链表
1.定义
顾名思义，就是只有一端指向的链表。
不带头结点的单向非循环链表
RT:
?
其中，每一个对象的next都存放的是逻辑上的下一个对象的地址。?
2.自定义一个单链表
创建一个MyLinkedList类
public class MyLinkedList {
static class ListNode {
public int val;//值
public ListNode next;//引用链接
public ListNode(int val) {
this.val = val;
}
}
public ListNode head;//头结点
}addFirst
头插
public void addFirst(int data){
ListNode cur = new ListNode(data);//new 一个需要插入的结点
cur.next = head;//将新结点的next指向head
head = cur;//让cur成为头结点
}addLast
尾插
如果你一开始有tail结点，那就十分容易：
public void addLast(int data) {
tail.next = new ListNode(data);
tail = tail.next;
}但没有tail结点也没关系，我们遍历一边即可，只是时间复杂度变为O（n），但也仍然高于顺序表的O（）
RT:
public void addLast(int data) {
if(head == null){
head = new ListNode(data);
return;
}
ListNode cur = head;
while(cur.next!=null){
cur = cur.next;
}
cur.next = new ListNode(data);
}addIndex(int index,int data)
在index下标前插入data
第一时间，依旧是判断index是否合法，那必须要用到size()函数，求出当前链表的长度。
public int size() {
ListNode cur = this.head;
int count = 0;
while (cur != null) {
count++;
cur = cur.next;
}
return count;
}RT:
public boolean addIndex(int index, int data) {
if (index == 0) {
ListNode insert = new ListNode(data);
insert.next = head;
head = insert;
return true;
}
if(index < 0 && index > size()){
return false;
}
ListNode cur = head;
while(index - 1 > 0){
cur = cur.next;//找到要插入的前一个结点
index--;
}
ListNode insert = new ListNode(data);
insert.next = cur.next;
cur.next = insert;
return true;
}obtain
是否包含
RT:
public boolean contains(int key) {
ListNode cur = head;
while(cur!=null){
if(cur.val == key){
return true;
}
cur = cur.next;
}
return false;
}remove
删除
RT:
public void remove(int key) {
if(head == null){
return;
}
if(head.val == key){
head = head.next;
}
ListNode pre = head;//找到前结点
while(pre.next != null){
if(pre.next.val == key){
break;
}
pre = pre.next;
}
ListNode cur = head;
while (cur != null) {
if(cur.val == key){
pre.next = cur.next;
}
cur = cur.next;
}
}removeAllKey
删除所有值为key的结点
由于与leetcode的203题一样，那我们直接做leetcode。
https://leetcode.cn/problems/remove-linked-list-elements/
具体思路：
1.定义两个结点，pre 和 cur，pre作为cur的前一个结点一直跟随cur，当遇到目标结点了，就直接pre.next = cur.next。
2.如此一来，我们把pre初始化为head，cur为head.next。然后将cur！=null作为判断条件，遍历一遍链表即可。
3.值得注意的是，如果把cur初始化为head.next，那么首结点就无法判断了，所以我们在末尾的时候，判断一次首结点是否是目标结点，那么就完成了。
public ListNode removeElements(ListNode head, int val) {
if(head == null){
return head;
}
ListNode pre = head;
ListNode cur = head.next;
while(cur!=null){
if(cur.val == val){
pre.next = cur.next;
cur = cur.next;
}else {
pre = cur;
cur = cur.next;
}
}
if(head.val == val){
head = head.next;
}
return head;
}
}
clear
清空
public void clear() {
this.head = null;
}解释：这里将head置为空，那么head所引用的对象head.next将因为无人引用而被回收，同样head.next的回收，又导致了head.next.next被回收，这样依次回收，链表就被清空了。
二、双链表
1.模拟实现
双链表的实现与单链表差距不大，主要的变化就是多了一个pre结点。直接上代码：
public class Linkedlist2 {
static class ListNode {
int val;
ListNode pre;
ListNode next;
public ListNode(int val) {
this.val = val;
}
}
public ListNode head;
public ListNode tail;
//头插法
public void addFirst(int data) {
ListNode cur = new ListNode(data);
if (this.head == null) {
this.head = cur;
this.tail = cur;
} else {
this.head.pre = cur;
cur.next = this.head;
head = cur;
}
}
//尾插法
public void addLast(int data) {
if (head == null) {
head = new ListNode(data);
tail = head;
} else {
ListNode cur = new ListNode(data);
tail.next = cur;
cur.pre = tail;
tail = cur;
}
}
//任意位置插入,第一个数据节点为0号下标
public void addIndex(int index, int data) {
//1、判断Index位置的合法性
//2、判断特殊位置，头插 和 尾插
//3、找到index位置节点的地址
if (index < 0 || index > size()) {
throw new PosOutInedx("INDEX IS ILLEGAL");
}
if (index == 0) {
addFirst(data);
return;
}
if (index == size()) {
addLast(data);
return;
}
ListNode find = this.head;
ListNode cur = new ListNode(data);
while (index > 0) {
find = find.next;
index--;
}
cur.pre = find.pre;
cur.next = find;
find.pre.next = cur;
find.pre = cur;
}
//查找是否包含关键字key是否在单链表当中
public boolean contains(int key) {
ListNode cur = head;
while (cur != null) {
if (cur.val == key) {
return true;
}
}
return false;
}
//删除第一次出现关键字为key的节点(注意链表的tail结点置空情况)
public void remove(int key) {
ListNode cur = head;
while (cur != null) {
if(cur.val == key){
if(cur == head){
head = head.next;
if(head==null){
tail = null;
}else {
head.pre = null;
}
}else if(cur == tail){
tail = tail.pre;
tail.next = null;
}else{
cur.pre.next = cur.next;
cur.next.pre = cur.pre;
}
return;
}
cur = cur.next;
}
}
//删除所有值为key的节点
public void removeAllKey(int key){
ListNode cur = head;
while (cur != null) {
if(cur.val == key){
if(cur == head){
head = head.next;
if(head==null){
tail = null;
}else {
head.pre = null;
}
}else if(cur == tail){
tail = tail.pre;
tail.next = null;
}else{
cur.pre.next = cur.next;
cur.next.pre = cur.pre;
}
}
cur = cur.next;
}
}
//得到单链表的长度
public int size() {
ListNode cur = head;
int count = 0;
while (cur != null) {
cur = cur.next;
count++;
}
return count;
}
public void display() {
ListNode cur = head;
while (cur != null) {
System.out.print(cur.val + " ");
cur = cur.next;
}
System.out.println();
}
public void clear() {
ListNode cur = head;
head = null;
tail = null;
while (cur != null) {
ListNode curNext = cur.next;
cur.pre = null;
cur.next = null;
cur = curNext;
}
}小结
????????正所谓 -- 基础不牢，地动山摇。虽然JAVA自带了自己的数据结构，但我们仍然需要在模拟实现上多下功夫，了解其底层的实现原理，多看源码，不仅可以加强自己的代码能力，也可以加深对数据结构这门学科的理解。
三、总结
? ? ? ? 我们通过链表的模拟实现，不难发现，链表的头插尾插效率很高，可以做到O（1），即使是随机插入，最坏的情况也是O(N)，所以，当我们的实际需求是频繁的插入删除时，同时如果要使用线性结构，请毫不犹豫使用链表。
????????但是，我们同样也发现了，如果我们要知道链表的第K个元素，我们必须去遍历它，而顺序表便没有这个烦恼，我们可以直接访问数组下标，在O（1）的时间复杂度内便可完成，所以，当我们实际需求是要查找，只要进行很少的插入删除操作时，最好使用顺序表。
以上便是本篇文章的全部内容。