前言
大家好，我是Maybe。最近在学习数据结构中的链表，自己手动实现了一个LinkedList。我想与大家分享一下。
思维导图
代码部分
package Constant;
public class constant {
public static final String INDEX_IS_WRONG="输入的下标不合法";
}
package utils;
public class IndexException extends RuntimeException{
public IndexException() {
super();
}
public IndexException(String message) {
super(message);
}
}
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();
}import Constant.constant;
import utils.IndexException;
public class LinkedList implements IList {
//1.定义一个内部类
static class ListNode{
public int val;
//类型写成了String,应该是ListNode的
public ListNode prev;
public ListNode next;
public ListNode(int val) {
this.val = val;
}
}
public ListNode head;
//这个就要给个尾了
public ListNode last;
@Override
public void addFirst(int data) {
if(head==null){
ListNode node=new ListNode(data);
head=last=node;
}else{
ListNode node=new ListNode(data);
node.next=head;
head.prev=node;
head=node;
}
}
@Override
public void addLast(int data) {
if(head==null){
ListNode node=new ListNode(data);
//写成了node=last=null了
head=last=node;
}else{
ListNode node=new ListNode(data);
last.next=node;
node.prev=last;
//这里要注意
last=last.next;
}
}
@Override
//在LinkedList中找到对应的cur，然后再cur之前插入
public void addIndex(int index, int data) {
int len=size();
if(index<0||index>len){
String msg= constant.INDEX_IS_WRONG+index;
throw new IndexException(msg);
}
if(index==0){
addFirst(data);
}else if(index==len){
addLast(data);
}else{
ListNode node=new ListNode(data);
ListNode cur=findIndex(index);
node.next=cur;
cur.prev.next=node;
node.prev=cur.prev;
cur.prev=node;
}
}
//在LinkedList中找到对应的cur
private ListNode findIndex(int index){
if(head==null){
return null;
}else{
ListNode cur=head;
while(index!=0){
cur=cur.next;
index--;
}
return cur;
}
}
@Override
public boolean contains(int key) {
if(head==null){
return false;
}else{
ListNode cur=head;
while(cur!=null){
if(cur.val==key){
return true;
}else{
cur=cur.next;
}
}
return false;
}
}
@Override
public void remove(int key) {
//1.先判断链表是否为空
if(head==null){
return;
}else{
ListNode cur=head;
while(cur!=null){
if(cur.val==key){
//1.考虑头删的情况
if(cur==head){
head=head.next;
//考虑如果链表中只有一个节点的情况
if(head!=null){
head.prev=null;
}
}else{
cur.prev.next=cur.next;//尾巴节点和中间节点共用
if(cur.next==null){//尾节点
last=last.prev;
}else{//中间节点
cur.next.prev=cur.prev;
}
}
return;
}
cur=cur.next;
}
}
}
@Override
public void removeAllKey(int key) {
if(head==null){
return;
}else{
ListNode cur=head;
while(cur!=null){
if(cur.val==key){
if(cur==head){
head=head.next;
//只有一个节点的情况要考虑
if(head!=null){
head.prev=null;
}
}else{
cur.prev.next=cur.next;
if(cur.next==null){
last=last.next;
}else{
cur.next.prev=cur.prev;
}
}
}
cur=cur.next;
}
}
}
@Override
public int size() {
if(head==null){
return 0;
}else{
ListNode cur=head;
int count=0;
while(cur!=null){
cur=cur.next;
count++;
}
return count;
}
}
@Override
public void display() {
if(head==null){
return;
}else{
ListNode cur=head;
while(cur!=null){
System.out.print(cur.val+" ");
cur=cur.next;
}
System.out.println();
}
}
@Override
public void clear() {
if(head==null){
return;
}else{
ListNode cur=head;
while(cur!=null){
ListNode curN=cur.next;
cur.prev=null;
cur.next=null;
cur=curN;
}
head=last=null;//最后要把head和last置为null
}
}
}import utils.IndexException;
public class Test {
public static void main(String[] args) {
LinkedList linkedList=new LinkedList();
linkedList.addLast(1);
linkedList.addLast(1);
linkedList.addLast(1);
linkedList.addLast(2);
linkedList.display();
// linkedList.addFirst(1);
// linkedList.addFirst(2);
// linkedList.addFirst(3);
// linkedList.addFirst(4);
// linkedList.display();
// int ret=linkedList.size();
// System.out.println(ret);
// try{
// linkedList.addIndex(2,100);
//
// }catch (IndexException e){
// e.printStackTrace();
// }
// linkedList.display();
// linkedList.remove(1);
// linkedList.display();
// linkedList.removeAllKey(1);
linkedList.clear();
linkedList.display();
}
}
结语
本次分享到此结束啦。希望可以帮到有需要的人！