LinkedList简介
Java LinkedList（链表）类似于 ArrayList，是一种常用的数据容器。 与 ArrayList 相比，LinkedList 的增加和删除的操作效率更高，而查找和修改的操作效率较低。
LinkedList底层是一个双向链表，如下：
一个双向链表有三个整数值: 数值、向后的节点链接、向前的节点链接
双向链表有头节点和尾结点。
因此要实现双向链表，我们就要用类将双向链表的各个部分给抽取出来
static class ListNode{
public int val;//数据域
public ListNode prev;//保存前一个节点的地址
public ListNode next;//保存后一个结点的地址
public ListNode(int val) {
this.val = val;
}
}
public ListNode head;//头节点
public ListNode tail;//尾结点
头插法创建链表
要用头插法建立双向链表，与单链表不同，双向链表的每一个结点都有三个域，因此我们要想清楚改哪个地方，看下图：
由图我我们可知，我们要改变插入结点的next域，要改变头节点的prev域，然后将插入结点的prev置为null，最后让头节点指向插入的结点，这样在头结点插入一个结点就完成了。
但这个只是一般情况下插入，还有一种特殊情况，就是遇到空链表。
如果是空链表的情况，那么头节点就是要插入的这个结点，尾节点也是要插入的这个结点。
public void addFirst(int data){
ListNode node = new ListNode(data);
//空链表
if(this.head == null){
this.head = node;
this.tail = node;
}else {
node.next = this.head;
this.head.prev = node;
this.head = node;
}
}
尾插法创建链表
看上图，我们可知用尾插法插入一个结点，要改变尾结点的next域，将要插入的next域置为空，将插入结点的prev域指向尾结点，再将尾节点指向要插入的结点就可以了。
同时也不要忘记考虑空链表的情况，与头插法相同，如果为空，那么要插入的这个结点就既是头结点也是尾结点。
public void addLast(int data){
ListNode node = new ListNode(data);
//空链表
if(this.head == null){
this.head = node;
this.tail = node;
}else {
this.tail.next = node;
node.prev = this.tail;
this.tail = node;
}
}
任意位置插入,第一个数据节点为0号下标
在插入数据时，我们首先要对要插入的位置index进行判断，判断index是否合法，index 位置合法才能插入数据。其次我们要考虑index在特殊位置，例如：在头节点和尾结点进行插入数据。
/**
* 任意位置插入,第一个数据节点为0号下标
* @param index
* 要对index位置判断是否合法
* index在特殊位置 -头插和尾插
* @param data
* @return
*/
public boolean addIndex(int index,int data){
if(index<0 || size()<index){
System.out.println("index位置不合法");
return false;
}
if(index == 0){
addFirst(data);
return true;
}
if(index == size()){
addLast(data);
return true;
}
ListNode node = new ListNode(data);
ListNode cur = findIndexListNode(index);
node.next = cur;
cur.prev.next = node;
node.prev = cur.prev;
cur.prev = node;
return false;
}
public ListNode findIndexListNode(int index){
ListNode cur = this.head;
while(index != 0){
cur = cur.next;
index--;
}
return cur;
}
查找是否包含关键字key是否在链表当中
查找是否包含关键字key，也就是遍历链表，与各个节点的数据域进行比较，如果相等就返回true，如果不相等，就返回false。
//查找是否包含关键字key是否在单链表当中
public boolean contains(int key){
ListNode cur = this.head;
while(cur != null){
if(cur.val == key){
return true;
}
cur= cur.next;
}
return false;
}
删除第一次出现关键字为key的节点
删除双向链表的节点,首先要明确我们要改那些值,看下图:
假设删除的是值为3的结点,那么此时要改变两个地方的值,就是删除结点前一个结点的next,以及后一个结点的prev.改完之后,就可以让值为2的结点直接找到值为4的结点,值为4的节点也可以直接找到值为2的结点.
然后我们还要考虑到删除的结点在特殊的位置,有两种情况:1.删除的结点在头节点或者是尾结点 2.只有一个结点
/**
* 删除第一次出现关键字为key的节点
* 可能会遇到的特殊情况
* 1.删除的节点在头或者尾
* 2.只有一个结点
* @param key
*/
public void remove(int key){
ListNode cur = this.head;
while(cur != null){
if(cur.val == key){
if(cur==head){//头节点
if(cur.next==null){//只有一个结点
this.head = null;
this.tail = null;
return;
}
this.head = head.next;
this.head.prev = null;
}else{
cur.prev.next = cur.next;
if(cur.next != null){
cur.next.prev = cur.prev;
}else{//删除的是尾结点的情况
this.tail = cur.prev;
}
}
return;
}else{
cur = cur.next;
}
}
}
删除所有值为key的节点
删除所有为key的结点,只需要在前面删除一个为key的结点代码上,把return删了就可以了.
//删除所有值为key的节点
public void removeAllKey(int key){
ListNode cur = this.head;
while(cur != null){
if(cur.val == key){
if(cur==head){
if(cur.next==null){
this.head = null;
this.tail = null;
return;
}
this.head = head.next;
this.head.prev = null;
}else{
cur.prev.next = cur.next;
if(cur.next != null){
cur.next.prev = cur.prev;
}else{
this.tail = cur.prev;
}
}
}
cur = cur.next;
}
}
得到链表的长度
得到链表的长度，实际上就相当于遍历了一边链表，如果当前节点不为空count就+1，最后return count就可以了。
//得到单链表的长度
public int size(){
ListNode cur = head;
int count = 0;
while(cur != null){
count++;
cur = cur.next;
}
return count;
}
打印链表
打印双向链表，我们可以从前往后进行打印，也可以从后往前打印。一般打印链表都是从前往后打印。具体代码实现如下：
public void display(){
ListNode cur = head;
while(cur != null){
System.out.print(cur.val+" ");
cur = cur.next;
}
}
清空链表
清空双向链表，不能直接将头节点和尾节点置为null
因为这是双向链表，直接置为null也可能会有别的结点引用,所以双向链表只能一个一个置空
public void clear(){
//error
/*this.head = null;
this.tail = null;*/
ListNode cur= this.head;
while(cur != null){
ListNode curNext = cur.next;
cur.prev = null;
cur.next = null;
cur = curNext;
}
this.head = null;
this.tail = null;
}
完整代码：
import java.util.List;
public class MyLinkedList {
static class ListNode{
public int val;
public ListNode prev;
public ListNode next;
public ListNode(int val) {
this.val = val;
}
}
public ListNode head;
public ListNode tail;
/**
* 无头双向链表实现
* @param data
*/
//头插法
public void addFirst(int data){
ListNode node = new ListNode(data);
//空链表
if(this.head == null){
this.head = node;
this.tail = node;
}else {
node.next = this.head;
this.head.prev = node;
this.head = node;
}
}
//尾插法
public void addLast(int data){
ListNode node = new ListNode(data);
//空链表
if(this.head == null){
this.head = node;
this.tail = node;
}else {
this.tail.next = node;
node.prev = this.tail;
this.tail = node;
}
}
/**
* 任意位置插入,第一个数据节点为0号下标
* @param index
* 要对index位置判断是否合法
* index在特殊位置 -头插和尾插
* @param data
* @return
*/
public boolean addIndex(int index,int data){
if(index<0 || size()<index){
System.out.println("index位置不合法");
return false;
}
if(index == 0){
addFirst(data);
return true;
}
if(index == size()){
addLast(data);
return true;
}
ListNode node = new ListNode(data);
ListNode cur = findIndexListNode(index);
node.next = cur;
cur.prev.next = node;
node.prev = cur.prev;
cur.prev = node;
return false;
}
public ListNode findIndexListNode(int index){
ListNode cur = this.head;
while(index != 0){
cur = cur.next;
index--;
}
return cur;
}
//查找是否包含关键字key是否在单链表当中
public boolean contains(int key){
ListNode cur = this.head;
while(cur != null){
if(cur.val == key){
return true;
}
cur= cur.next;
}
return false;
}
/**
* 删除第一次出现关键字为key的节点
* 可能会遇到的特殊情况
* 1.删除的节点在头或者尾
* 2.只有一个结点
* @param key
*/
public void remove(int key){
ListNode cur = this.head;
while(cur != null){
if(cur.val == key){
if(cur==head){
if(cur.next==null){
this.head = null;
this.tail = null;
return;
}
this.head = head.next;
this.head.prev = null;
}else{
cur.prev.next = cur.next;
if(cur.next != null){
cur.next.prev = cur.prev;
}else{
this.tail = cur.prev;
}
}
return;
}else{
cur = cur.next;
}
}
}
//删除所有值为key的节点
public void removeAllKey(int key){
ListNode cur = this.head;
while(cur != null){
if(cur.val == key){
if(cur==head){
if(cur.next==null){
this.head = null;
this.tail = null;
return;
}
this.head = head.next;
this.head.prev = null;
}else{
cur.prev.next = cur.next;
if(cur.next != null){
cur.next.prev = cur.prev;
}else{
this.tail = cur.prev;
}
}
}
cur = cur.next;
}
}
//得到单链表的长度
public int size(){
ListNode cur = head;
int count = 0;
while(cur != null){
count++;
cur = cur.next;
}
return count;
}
public void display(){
ListNode cur = head;
while(cur != null){
System.out.print(cur.val+" ");
cur = cur.next;
}
}
public void clear(){
//error
this.head = null;
this.tail = null;
/* ListNode cur= this.head;
while(cur != null){
ListNode curNext = cur.next;
cur.prev = null;
cur.next = null;
cur = curNext;
}
this.head = null;
this.tail = null;*/
}
}
总结:
LinkedList作为Java中的一个重要集合,底层是个双向链表,我只是模拟实现了一些简单的功能,大家如果要研究LinkedList底层到底是怎么实现的,大家开始去看源码比较好.
![现有一个接口DataOperation定义了排序方法sort(int[])和查找方法search(int[],int)，已知类QuickSort的quickSort(int[])方法实现了快速排序算法](https://ucc.alicdn.com/b3c447iaqrtq2_20240813_8507e56fc1e0475c88702b767789ed11.png?x-oss-process=image/resize,h_160,m_lfit)
