链表简单实现

最近在看HashMap的底层实现时发现 HashMap是基于数组和链表实现的，数组我们应该都熟悉,链表在学习List 的实现类的

时候 LinkedLIst 的底层实现也是基于链表的,看来链表数据结构还是挺重要的,于是参考LinkedList自己写了一个简单的链表

在实现链表之前我们首先要了解一下链表的概念,我的理解是链表实际上就是由若干个节点连接而成的一种数据结构,

首先节点中包括 date 和 next(可以看做是指针，用于指向下一个节点) 还有一个最重要的是 first引用(本质上也是一个节点,只不过这是一个特殊的节点把它当做一条线上所有节点的头部,也就是第一个节点)

//先创建一个节点类我的理解是链表实际上就是由若干个节点连接而成的一种数据结构,

Node.class

package 链表实现;

/**
* Created by 一枝叶 on 2019/3/15.
*/
public class Node {
int date; //储存的数据
Node next; //节点的引用下一个节点

// public Node(int date, Node node) {
// this.date = date;
// this.node = node;
// }

public Node(int date) {
this.date = date;
}

public int getDate() {
return date;
}

public void setDate(int date) {
this.date = date;
}

public Node getNext() {
return next;
}

public void setNext(Node next) {
this.next = next;
}
}

自定义的链表 myLink.class 这里只写了增删的方法

package 链表实现;

import java.util.ArrayList;
import java.util.List;

/**
* Created by 一枝叶 on 2019/3/15.
*/
public class MyLink {

Node first = null; //整张表的引用

//向链表中插入数据
public void add(int date) {

//新建一个节点
Node newNode = new Node(date);

//如果链表的first引用为Null则将第一个添加元素的节点设置为first引用
if (first == null) {
first = newNode;
return;
}

//如果链表的first引用不为Null则拿到first引用的节点对象
Node temp = first;

//从first引用开始查找插入点
while (temp.next != null) {
temp = temp.next;
}

temp.next = newNode; //重新指向

}

//返回节点长度
public int length() {
Node f = first;
int count = 0;
while (f != null) {
count++;
f = f.next;
}
return count;
}

//从链表中删除数据(删除第index个数据)
public void deleteNode(int index) {
Node p = null;//保存父节点
Node f = first; //得到first引用
int i = -1; //记录节点位置从零开始

while (f != null) {

i++;

//如果是删除第一个节点则它的后一个节点设置为first
if (i == 0) {

if (f.date == index) {
first = f.next;
return;
}

} else if (i == length() - 1) { //如果是删除最后一个节点则它前一个节点指向null

if (f.date == index) {
p.next = null;
return;
}

} else {
if (f.date == index) {
p.next = f.next;
return;
}
}

p = f;//保留本次节点作为下一节点的父节点
f = f.next; //获取下一个节点

}
}

//遍历链表
public void getList() {
Node f = first;
while (f != null) {
System.out.println(f.date);
f = f.next;
}

}
}
测试类 test.class

package 链表实现;

/**
* Created by 一枝叶 on 2019/3/15.
*/
public class Test {
public static void main(String[] args) {
MyLink myLink=new MyLink();

//增加数据
myLink.add(1);
myLink.add(2);
myLink.add(3);
System.out.println("删除前元素长度:"+myLink.length());

//遍历链表
System.out.println("删除元素前遍历列表--------");
myLink.getList();
//删除数据
//myLink.deleteNode(1);
System.out.println("删除元素----------------");

myLink.deleteNode(2);
System.out.println("删除完成----------------");

System.out.println("删除后的长度:"+myLink.length());
System.out.println("删除后的遍历元素:");
myLink.getList();

}
}
执行结果:

删除前元素长度:3
删除元素前遍历列表--------
1
2
3
删除元素----------------
删除完成----------------
删除后的长度:2
删除后的遍历元素:
1
3

————————————————
版权声明：本文为CSDN博主「EinBlatt」的原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/Ein_Blatt/article/details/88616205