✨hello,愿意点进来的小伙伴们,你们好呐!
✨ 🐻🐻系列专栏:【数据结构】
🐲🐲本篇内容:简单实现双向链表API
🐯🐯作者简介:一名现大二的三非编程小白
前言
链表在Java中是很常用的数据结构,我们想将链表学好的话还是得知道链表的底层是如何实现各种API的,下面让我来简单实现一下一些常用的API。
o
1. 创建 MyLinkedList 类,创建ListNode内部类。
我们要在MyLinkedList类中创建内部类 ListNode 。且要定义 head 与 tail 节点来指向链表的头部与尾部。
public class MyLinkedList02 {
static class ListNode{
public int val;
public ListNode next;
public ListNode prev;
public ListNode(int val) {
this.val = val;
}
}
public ListNode head;
public ListNode tail;
}
2.打印链表中的所有节点元素
public void display(){
ListNode cur = head;
while(cur != null){
System.out.print(cur.val + " ");
cur = cur.next;
}
}
3. 计算所有链表长度
public int size(){
if(head == null){
return -1;
}
int count = 0;
ListNode cur = head;
while(cur != null){
count++;
cur = cur.next;
}
return count;
}
3.查找链表中是否有该元素
public boolean contains(int key){
if(head == null){
return false;
}
ListNode cur = head;
while(cur != null){
if(cur.val == key){
return true;
}
cur = cur.next;
}
return false;
}
4.在链表头部插入元素
思路:
- 我们要先判断链表是否为null。
- 如果不为null,就将head的前驱指向要插入的结点,将要插入的节点的后指向head,head往前移动一位。
public void addFirst(int data){
ListNode node = new ListNode(data);
if(head == null){
this.head = node;
this.tail = node;
}else{
head.prev = node;
node.next = head;
head = node;
}
}
5.在链表尾部插入元素
public void addList(int data){
ListNode node = new ListNode(data);
if(head == null){
this.head = node;
this.tail = node;
}else{
this.tail.next = node;
node.prev = tail;
tail = node;
}
}
6.往链表中插入元素
public void addIndex(int index,int data){
//1.先判断index的合法性
if(index < 0 || index > size()){
throw new IndexWrongFullException("index不合法");
}
//2.判断是否是头插或者尾插法
if(index == 0){
addFirst(index);
}
if(index == size()){
addList(data);
}
//3.在中间插入元素
ListNode cur = findIndexNode(index);
ListNode node = new ListNode(data);
node.next = cur;
cur.prev.next = node;
node.prev = cur.prev;
cur.prev = node;
}
7.找到index位置的元素
public ListNode findIndexNode(int index){
ListNode cur = head;
while(index != 0){
cur = cur.next;
index--;
}
return cur;
}
8.除第一次出现的key
public void remove(int key){
ListNode cur = head;
while(cur != null){
if(cur.val == key){//找到要删除的元素
if(cur == head){//判断该元素是否为链表头元素
head = head.next;//是的话 先将头节点指向下一个节点
if(head != null){//判断目前的头节点是否为null
head.prev = null;//如果不是 将头节点的前驱置空
}else{
tail = head;//是 尾节点指向头节点
}
}else{//不是头节点
cur.prev.next = cur.next;//将删除目标节点的前驱指向 后一个节点
if(cur != tail){//判断删除的是否为尾节点
cur.next.prev = cur.prev;//
}else{//是 将尾节点向前移动一位
tail = tail.prev;
}
}
return;
}
cur = cur.next;
}
}
9.删除所有出现的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 = head;
}else{
head.prev = null;
}
}else{
cur.prev.next = cur.next;
if(cur == tail){
tail = tail.prev;
}else{
cur.next.prev = cur.prev;
}
}
}
cur = cur.next;
}
}
10. 置空链表
public void clear(){
ListNode cur = head;
while(cur != null){
ListNode curNext = cur.next;
cur.prev = null;
cur.next = null;
cur = curNext;
}
head = null;
tail = null;
}
本文含有隐藏内容,请 开通VIP 后查看