【单链表的模拟实现Java】
1. 了解单链表的功能2. 模拟实现单链表的功能2.1 单链表的创建2.2 链表的头插2.3 链表的尾插2.3 链表的长度2.4 链表的打印2.5 在指定位置插入2.6 查找2.7 删除第一个出现的节点2.8 删除出现的所有节点2.9 清空链表 3. 正确使用模拟单链表
1. 了解单链表的功能
下面为链表的一些基本功能，该文章也将详细讲解下列方法的模拟实现。
2. 模拟实现单链表的功能
2.1 单链表的创建
首先要先完成链表这一对象的创建，然后类中包含有：链表中节点这一对象、相关功能的方法（由于后续还要实现双向链表的相关方法，所以这里使用接口）
下面是代码实现
IList接口
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();}Mylinkedlist链表
public class Mylinkedlist implements IList{ //创建一个对象——链表中的节点 static class listnode{ public int val;//节点中储存的数值 public listnode next;//下一节点的地址 public listnode(int val) { this.val = val; } } public listnode head;//指向第一个节点的指针 @Override public void addFirst(int data) { } @Override public void addLast(int data) { } @Override public void addIndex(int index, int data) { } @Override public boolean contains(int key) { return false; } @Override public void remove(int key) { } @Override public void removeAllKey(int key) { } @Override public int size() { return 0; } @Override public void clear() { } @Override public void display() { }}2.2 链表的头插
public void addFirst(int data) { listnode p=new listnode(data); p.next=head; head=p; }2.3 链表的尾插
链表的尾插分两种情况
链表为空，head没有next链表不为空首先我们先判断链表是否为空
public boolean isempty(){ if(head==null){ return true; }else{ return false; } }之后实现尾插
public void addLast(int data) { listnode p=new listnode(data); if(isempty()){ head=p; }else{ //遍历找到最后节点 listnode pcur=head; while(pcur.next!=null){ pcur=pcur.next; } //最后节点的指针指向p pcur.next=p; } }2.3 链表的长度
public int size() { listnode pcur=head; int count=0; while(pcur!=null){ pcur=pcur.next; count++; } return count; }2.4 链表的打印
public void display() { listnode pcur=head; while(pcur!=null){ System.out.print(pcur.val+" "); pcur=pcur.next; } }2.5 在指定位置插入
在指定位置插入分三种情况
该指定位置超出链表的长度，出现异常该位置为链表头部或尾部，直接使用头插和尾插正常情况下面是代码实现
public void addIndex(int index, int data) { if(index>size()||index<0){ System.out.println("输入异常"); return; } if(index==0) addFirst(data); else if (index==size()) addLast(data); else{ listnode p=new listnode(data); listnode pcur=head; //找到指定位置前一个位置 for(int i=0;i<index-1;i++){ pcur=pcur.next; } p.next=pcur.next; pcur.next=p; } }2.6 查找
public boolean contains(int key) { listnode pcur=head; while(pcur!=null){ if(pcur.val==key){ return true; } pcur= pcur.next; } return false; }2.7 删除第一个出现的节点
删除主要讨论两种情况
删除节点为第一个节点删除节点为中间节点或尾节点 public void remove(int key) { listnode pcur=head; if(pcur==null) return; //第一个节点 if(pcur.val==key){ pcur=pcur.next; head=pcur; return; } //中间节点或尾节点 while(pcur!=null){ if(pcur.next!=null&&pcur.next.val==key){ pcur.next=pcur.next.next; return; }else{ pcur= pcur.next; } } }2.8 删除出现的所有节点
删除出现的所有节点与删除出现的第一个节点有很多相似的地方，代码需要更改的有两点
第一个节点的情况，将if语句改为while语句中间节点或尾节点，删除后不返回，继续循环，知道遍历完整个链表 public void removeAllKey(int key) { listnode pcur=head; if(pcur==null) return; //第一个节点 while(pcur.val==key){ pcur=pcur.next; head=pcur; } while(pcur!=null){ if(pcur.next!=null&&pcur.next.val==key){ pcur.next=pcur.next.next; }else{ pcur= pcur.next; } } }2.9 清空链表
public void clear() { //遍历逐一释放 while(head!=null){ listnode pcur=head; head=head.next; pcur=null; } }3. 正确使用模拟单链表
到这里上面的基础功能已经全部实现，现在就开始使用一下。
main方法如下所示
public static void main(String[] args) { Mylinkedlist l=new Mylinkedlist(); //头插 l.addFirst(1); l.addFirst(1); l.addFirst(1); l.addFirst(2); //尾插 l.addLast(3); l.addLast(3); l.addLast(3); l.addLast(4); //指定位置插入 l.addIndex(4,5); l.addIndex(6,5); System.out.print("原链表："); l.display(); //删除第一次出现的5 l.remove(5); System.out.print("删除第一次出现的5: "); l.display(); //删除所有出现的3 l.removeAllKey(3); System.out.print("删除所有出现的3: "); l.display(); //清空链表 l.clear(); System.out.print("清空链表："); l.display(); }结果：
该文章到这里就结束了，希望对你有所帮助！