文章目录
- 创建一个ILindkedList接口创建方法(模拟实现链表方法)
- 创建MyLinkedList来实现接口的方法
- 创建链表节点
- addFirst方法（新增头部属性）
- addLast方法（新增到末尾一个属性）
- remove方法（删除指定属性）
- addIndex方法（任意位置添加一个元素属性）
- removeAll（删除所有指定元素）
- display打印
- contains（链表中包含某个元素）
- size（获取链表元素的数量）
- clean（清空）
- MyLinkedList代码如下：
- Test代码：
- **链表是通过逻辑储存的方式通过节点的引用来获取元素值，每个节点包含两个部分 首先第一部分是value元素值。 第二部分是next来获取下个节点的地址，通过next来串联各个地址获取其中的value元素
有序数组如果想要新增或者删减元素需要从头开始遍历逐个进行覆盖确保有序数组中的有序,时间复杂度为O(m*n)。
链表的复杂度相对有序数组要方便他的时间复杂度分别是O(1)和O(N)。 **
创建一个ILindkedList接口创建方法(模拟实现链表方法)
public interface ILinkedList {
//首位置新增元素
public void addFirst(int data);
//最后位置新增元素
public void addLast(int data);
//在指定位置新增元素
public void addIndex(int index,int data);
//在链表中删除key元素
public void remove(int key);
//删除所有key的元素
public void removeAll(int key);
//打印链表元素
public void display();
//是否包含data
public boolean contains(int data);
//获取链表中元素的大小
public int size();
void clean();
}
创建MyLinkedList来实现接口的方法
import javax.xml.soap.Node;
public class MyLinkedList implements ILinkedList{
//创建一个static内部类来初始化节点属性
static class NodeList{
//元素值
public int value;
//节点指向的下一个地址
public NodeList next;
//构造方法只给value通过这个值来next下一个节点
public NodeList(int value) {
this.value = value;
}
}
创建链表节点
//这里可以尝试创建一个链表
public void createLinkedList(){
NodeList node1=new NodeList(23);
NodeList node2=new NodeList(25);
NodeList node3=new NodeList(38);
NodeList node4=new NodeList(55);
//通过获取的对象来访问next链接下一个节点实现链接
node1.next=node2;
node2.next=node3;
node3.next=node4;
//这里node4的next节点为空值
//head作为头部来访问各个节点
this.head=node1;
}
addFirst方法（新增头部属性）
@Override
public void addFirst(int data) {
//增加一个元素到链表中,增加到头部
//将data元素放入到类中
NodeList node=new NodeList(data);
NodeList cur=this.head;
//这里node.next来获取头部地址
node.next=head;
//将node赋给head
head=node;
}
addLast方法（新增到末尾一个属性）
@Override
public void addLast(int data) {
//增加一个元素到末尾
NodeList node=new NodeList(data);
NodeList cur=this.head;
//这里我们查找最后一个位置的next节点是否为null，如果是null；
while(cur.next!=null){
cur = cur.next;
}
//循环出来cur.next的节点为null
cur.next=node;
}
remove方法（删除指定属性）
@Override
public void remove(int key) {
//删除指定元素的next地址节点
if(this.head==null){
return;
}
//得到前缀
NodeList cur = findRemoveKey(key);
//判断返回值是否是空的
if(cur==null){
System.out.println("未找到该元素"+key);
return;
}
//将cur.next给到dele得到节点
NodeList dele=cur.next;
//将后一个节点的next给到cur.next从而指向其他节点dele原有节点消失
cur.next=dele.next;
}
private NodeList findRemoveKey(int key){
NodeList cur=this.head;
//cur.next不等于null数值
while(cur.next!=null){
if(cur.next.value==key){
return cur;
}
//cur.next节点获取下一个cur
cur = cur.next;
}
return null;
}
addIndex方法（任意位置添加一个元素属性）
removeAll（删除所有指定元素）
@Override
public void removeAll(int key) {
if(this.head==null){
return;
}
NodeList pre=this.head;
NodeList cur=pre.next;
//cur！=null说明有数据
while(cur!=null){
//value值为key进入循环
if(cur.value==key){
//pre的下个节点为cur的下一个节点，取消掉cur=key这个节点的链接
pre.next=cur.next;
cur=cur.next;
}else{
//如果不等于pre要跳到cur的位置来继续作为前一项
pre=cur;
//cur获取下一项
cur=cur.next;
}
}
//不要忽略头部，如果是key要替换掉
if(this.head.value==key){
this.head=this.head.next;
}
}
@Override
public void addIndex(int index, int data)throws ErrorRuntimeExcepetion {
//给一个位置，放入data元素
//如果index的值小于0或者大于本身长度抛出异常显示下标
try {
if(index<0||index>size()){
throw new ErrorRuntimeExcepetion("范围不准确"+index);
}
}catch (ErrorRuntimeExcepetion e){
e.printStackTrace();
return;
}
//如果index的位置是0或者index的位置是最后一个
if(index==0){
addFirst(data);
}
if(index==size()){
addLast(data);
}
//走到这里index的值为其范围内容，首先获取index-1的位置
NodeList cur = searchPre(index);
//生成data元素链表
NodeList node=new NodeList(data);
if(cur==null){
return;
}
//将原来cur.index的地址赋值给node.index来后移
node.next=cur.next;
//将现在的cur.index的地址指向node
cur.next=node;
}
private NodeList searchPre(int index){
NodeList cur=this.head;
//求一个index-1的范围
int count=0;
while(count<index-1){
cur=cur.next;
count++;
}
//获取到index-1位置的cur
return cur;
}
display打印
@Override
public void display() {
//创建一个对象接收head值，来进行打印
NodeList cur=this.head;
//cur不等于null
while(cur!=null){
//通过cur引用value来打印元素
System.out.print(cur.value+" ");
//通过next中下一个节点的地址来访问元素
cur=cur.next;
}
System.out.println();
}
contains（链表中包含某个元素）
@Override
public boolean contains(int data) {
//链表中是否包含data
NodeList cur=this.head;
if(cur.value==data){
//如果value是data返回true
return true;
}else{
while(cur.next!=null){
//循环每个节点判断是否为data
if(cur.next.value==data){
return true;
}
cur=cur.next;
}
}
return false;
}
size（获取链表元素的数量）
@Override
public int size() {
//获取链表的元素大小
NodeList cur = this.head;
//如果cur中为null没有任何元素大小是0
if (cur == null) {
return 0;
}
int count=0;//计数
while(cur!=null){
count++;
cur=cur.next;
}
return count;
}
clean（清空）
@Override
public void clean() {
if(this.head==null){
return;
}
//将每个节点置为空属性并且回收
NodeList cur=this.head;
while(cur!=null){
NodeList curNext=cur.next;
cur.next=null;
cur=curNext;
}
//置空null
this.head=null;
}
MyLinkedList代码如下：
import javax.xml.soap.Node;
public class MyLinkedList implements ILinkedList{
//创建一个static内部类来初始化节点属性
static class NodeList{
//元素值
public int value;
//节点指向的下一个地址
public NodeList next;
//构造方法只给value通过这个值来next下一个节点
public NodeList(int value) {
this.value = value;
}
}
//创建一个带头链表来获取当前的节点第一个元素
public NodeList head;
//这里可以尝试创建一个链表
public void createLinkedList(){
NodeList node1=new NodeList(23);
NodeList node2=new NodeList(25);
NodeList node3=new NodeList(38);
NodeList node4=new NodeList(55);
//通过获取的对象来访问next链接下一个节点实现链接
node1.next=node2;
node2.next=node3;
node3.next=node4;
//这里node4的next节点为空值
//head作为头部来访问各个节点
this.head=node1;
}
@Override
public void addFirst(int data) {
//增加一个元素到链表中,增加到头部
//将data元素放入到类中
NodeList node=new NodeList(data);
NodeList cur=this.head;
//这里node.next来获取头部地址
node.next=head;
//将node赋给head
head=node;
}
@Override
public void addLast(int data) {
//增加一个元素到末尾
NodeList node=new NodeList(data);
NodeList cur=this.head;
//这里我们查找最后一个位置的next节点是否为null，如果是null；
while(cur.next!=null){
cur = cur.next;
}
//循环出来cur.next的节点为null
cur.next=node;
}
@Override
public void remove(int key) {
//删除指定元素的next地址节点
if(this.head==null){
return;
}
//得到前缀
NodeList cur = findRemoveKey(key);
//判断返回值是否是空的
if(cur==null){
System.out.println("未找到该元素"+key);
return;
}
//将cur.next给到dele得到节点
NodeList dele=cur.next;
//将后一个节点的next给到cur.next从而指向其他节点dele原有节点消失
cur.next=dele.next;
}
private NodeList findRemoveKey(int key){
NodeList cur=this.head;
//cur.next不等于null数值
while(cur.next!=null){
if(cur.next.value==key){
return cur;
}
//cur.next节点获取下一个cur
cur = cur.next;
}
return null;
}
@Override
public void removeAll(int key) {
if(this.head==null){
return;
}
NodeList pre=this.head;
NodeList cur=pre.next;
//cur！=null说明有数据
while(cur!=null){
//value值为key进入循环
if(cur.value==key){
//pre的下个节点为cur的下一个节点，取消掉cur=key这个节点的链接
pre.next=cur.next;
cur=cur.next;
}else{
//如果不等于pre要跳到cur的位置来继续作为前一项
pre=cur;
//cur获取下一项
cur=cur.next;
}
}
//不要忽略头部，如果是key要替换掉
if(this.head.value==key){
this.head=this.head.next;
}
}
@Override
public void addIndex(int index, int data)throws ErrorRuntimeExcepetion {
//给一个位置，放入data元素
//如果index的值小于0或者大于本身长度抛出异常显示下标
try {
if(index<0||index>size()){
throw new ErrorRuntimeExcepetion("范围不准确"+index);
}
}catch (ErrorRuntimeExcepetion e){
e.printStackTrace();
return;
}
//如果index的位置是0或者index的位置是最后一个
if(index==0){
addFirst(data);
}
if(index==size()){
addLast(data);
}
//走到这里index的值为其范围内容，首先获取index-1的位置
NodeList cur = searchPre(index);
//生成data元素链表
NodeList node=new NodeList(data);
if(cur==null){
return;
}
//将原来cur.index的地址赋值给node.index来后移
node.next=cur.next;
//将现在的cur.index的地址指向node
cur.next=node;
}
private NodeList searchPre(int index){
NodeList cur=this.head;
//求一个index-1的范围
int count=0;
while(count<index-1){
cur=cur.next;
count++;
}
//获取到index-1位置的cur
return cur;
}
@Override
public void display() {
//创建一个对象接收head值，来进行打印
NodeList cur=this.head;
//cur不等于null
while(cur!=null){
//通过cur引用value来打印元素
System.out.print(cur.value+" ");
//通过next中下一个节点的地址来访问元素
cur=cur.next;
}
System.out.println();
}
@Override
public boolean contains(int data) {
//链表中是否包含data
NodeList cur=this.head;
if(cur.value==data){
//如果value是data返回true
return true;
}else{
while(cur.next!=null){
//循环每个节点判断是否为data
if(cur.next.value==data){
return true;
}
cur=cur.next;
}
}
return false;
}
@Override
public int size() {
//获取链表的元素大小
NodeList cur = this.head;
//如果cur中为null没有任何元素大小是0
if (cur == null) {
return 0;
}
int count=0;//计数
while(cur!=null){
count++;
cur=cur.next;
}
return count;
}
@Override
public void clean() {
if(this.head==null){
return;
}
//将每个节点置为空属性并且回收
NodeList cur=this.head;
while(cur!=null){
NodeList curNext=cur.next;
cur.next=null;
cur=curNext;
}
//置空null
this.head=null;
}
}
Test代码：
public class Test {
public static void main(String[] args) {
MyLinkedList myLinkedList=new MyLinkedList();//这里创建链表对象
// myLinkedList.createLinkedList();//访问创建的链表
myLinkedList.addFirst(10);
myLinkedList.addFirst(10);
myLinkedList.addLast(10);
myLinkedList.addLast(10);
myLinkedList.addIndex(3,39);
myLinkedList.addIndex(5,10);
System.out.println(myLinkedList.contains(39));
myLinkedList.display();
myLinkedList.remove(39);
myLinkedList.removeAll(10);
myLinkedList.display();
myLinkedList.clean();
myLinkedList.addFirst(1);
myLinkedList.display();
System.out.println("链表中的元素大小为"+myLinkedList.size());
}
}
#运行结果
