手写单向链表(Java实现)
程序员文章站
2024-03-18 11:47:28
...
手写单向链表(Java实现)
大三下学期开始自学Java,在51cto上找了一套Java基础课程,是李兴华老师讲的,我感觉课程不错而且免费就跟着这套教程学;JavaSE学了一大半时,李老师花很大的篇幅讲解了怎样手写ArrayList(链表),当时我反复看视频还是理解不了有些功能是怎样实现的;遂放下去学别的东西。一晃毕业一年了,想到了这个事,于是找出当年的课程倍速看完,将链表成功的实现了。
在上代码之前,必须感谢一下李兴华老师(虽然他不会看我这篇博客),李老师算是我编程的引路人。代码中有虽然有注释,但有些地方理解难度还是不小的,阅读链表的实现代码按照Link接口中的功能顺序来阅读,实现代码(LinkImpl)中的功能顺序比较乱。这个链表的实现大量的用到了递归方法,很多地方都使用了this关键字,如果理解了这些this关键字在不同的地方代表的是什么,那就差不多理解了这个链表的实现原理了。好了,直接上代码,看完如果觉得有所收获,请顺手点个赞。
public interface Link {
void add(Object data);//数据增加
int size();//取得元素个数
boolean isEmpty();//判断是否为空集合
boolean contains(Object obj);//判断是否有指定的值
Object get(int index);//根据索引取得指定的数据
void set(int index,Object obj);//修改制定索引位置上的数据
void remove(Object data);//数据删除操作
void clear();//清空链表
Object[] toArray();//返回数据,转换成对象数据
}
/**
* 简单的单向链表
*/
public class LinkImpl implements Link{
private class Node{ //使用私有内部类,防止外部使用此类
private Object data; //存储数据
private Node next; //保存下一个节点
public Node(Object data){
this.data=data;
}
public void addNode(Node newNode){
if(this.next==null){
this.next=newNode;
}else {
this.next.addNode(newNode); //递归调用,将新节点添加到最后
}
}
public boolean containsNode(Object obj){
if(this.data.equals(obj)){
return true;
}else {//继续向下查找
if(this.next!=null){//当前节点之后还有下一个节点
return this.next.containsNode(obj);
}else {
return false;
}
}
}
public void toArrayNode(){
LinkImpl.this.retData[LinkImpl.this.foot++]=this.data;
if(this.next!=null){
this.next.toArrayNode();
}
}
public void removeNode(Node previous,Object data){
if(this.data.equals(data)){//为当前要删除的节点
previous.next=this.next;//空出当前节点
}else {
this.next.removeNode(this,data);
}
}
/**
* 设置值
*/
public void setNode(int index,Object data){
if(LinkImpl.this.foot++==index){
this.data=data;
}else {
this.next.setNode(index,data);
}
}
/**
* 依次判断每一个索引值的操作形式
* @param index
* @return
*/
public Object getNode(int index){//传递索引的序号
if(LinkImpl.this.foot++==index){//当前的索引为要查找的索引
return this.data;//返回当前节点对象,foot从0开始,第二次调用getNode()时this=root.next
}else {
return this.next.getNode(index);
}
}
}
//******************************************************
private Node root; //根节点
private int count=0;//保存元素的个数
private int foot=0;//操作的索引脚标
private Object[] retData=null;
@Override
public void add(Object data) {
if(data==null){
return;//结束调用
}
Node newNode=new Node(data); //创建新节点
if(root==null){
this.root=newNode;
}else {//应该交由Node类负责处理
this.root.addNode(newNode);
}
this.count++;
}
@Override
public void set(int index, Object obj) {
if(index>=this.count){//索引不存在
return;
}
this.root.setNode(index,obj);
}
@Override
public boolean contains(Object obj) {
if(this.root==null){ //没有集合数据
return false;
}
return this.root.containsNode(obj);
}
@Override
public Object get(int index) {
if(index>=this.count){ //索引不存在
return null;
}
this.foot=0;//查询之前执行依次清零操作
return this.root.getNode(index);
}
@Override
public void remove(Object data) {
if(this.contains(data)){//数据如果存在则删除
if(this.root.data.equals(data)){ //根元素为要删除的元素
this.root=this.root.next; //第二个元素作为要删除的元素
}else {//根元素不是要删除的元素
this.root.next.removeNode(this.root,data);
}
this.count--;
}
}
@Override
public Object[] toArray() {
if(this.root==null){
return null;
}
retData=new Object[this.count];
this.foot=0;
this.root.toArrayNode();
return this.retData;
}
@Override
public void clear() {
this.root=null;
this.count=0;
System.gc();//回收内存空间
}
@Override
public int size() {
return this.count;
}
@Override
public boolean isEmpty() {
return this.root==null;
}
}
上一篇: Python 自定义队列
下一篇: 循环队列的元素个数计算公式