教育行业A股IPO第一股(股票代码 003032)

全国咨询/投诉热线:400-618-4000

java数据结构-单链表的数据操作及特性

更新时间:2018年12月07日11时28分 来源:传智播客 浏览次数:

# 数据结构-单链表的数据操作及特性

数据结构-单链表的数据操作及特性

## 概述

​ 上一章中,我们已经入门了单链表的添加数据以及查询数据打印了,那么当我们存储了数据,要删除的时候怎么办呢?这章,我们来看看如何删除数据。

![](image\image1.png)

## 根据数据删除节点

### 分析

​ 根据数据删除节点,

1. 首先:删除数据分三种情况,1.删除的节点是头节点 2.删除的节点为尾节点 3.删除的节点是中间节点

2. 其次:需要获取要删除的数据所对应的节点以及他的前一个节点

3. 删除节点,需要将链表的长度扣减增加节点需要长度增加。

### 实现

#### 修改增加方法,增加长度属性

```java

private transient int size = 0;// 单列表的长度

/**

* 从尾部添加一个节点

*

* @param data

* 要添加的节点的数据

*/

public void add(Object data) {

// 1.构建一个节点对象

Node node = new Node(data);

if (head == null) {

// 2.判断链表中是否为空 如果为空 则新增的节点变成头节点

head = node;

} else {

// 3.如果链表不为空,则需要查询到尾部节点

Node rear = findRearNode();

// 4.向尾部节点添加一个节点

rear.next = node;// rear肯定不为空

}

size++;

}

// 获取链表的长度

public int size() {

return size;

}

```

#### 编写删除的代码

```java

// 删除链表中的数据

public void removeObject(Object data) {

// 赋值为临时对象

Node temp = head;

//记录要删除的节点的前一个节点

Node prev = temp;

if (data != null)

while (temp != null) {

if (data.equals(temp.data) && temp.data.hashCode()==data.hashCode()) {

//如果删除的是头节点

if(temp==head){

head=temp.next;//

//如果删除的是尾部节点

}else if(temp.next==null){

prev.next=null;

//如果删除的是中间节点

}else{

prev.next=temp.next;

}

size--;

break;

}

prev=temp;

//循环遍历

temp=temp.next;

}

}

```

代码解释:先查询数据在链表中是否有,需要循环遍历,当数据一致 并且hashcode一致时,我们才认为这才是两个相等的数据对象;接着 获取前一个节点对象。

## 根据索引删除节点

### 分析

​ 根据索引删除节点,也就是说从第几个位置开始删除,默认第一个位置索引为0 以此类推。

1. 首先:删除的节点的索引不能超过总长度

2. 其次:删除的节点 要先找到对应节点数据 再删除。

### 实现

```java

/**

* 根据指定的索引来删除链表中的数据

* @param index

*/

public void removeIndexObject(int index) {

int count=0;

if(index<0 ||index >=size){

System.out.println("越界");

return;

}

Node temp = head;

//记录前一个节点

Node prev = temp;

while (temp != null) {

if(count==index){

if(index==0){//说明删除的是头节点

head = temp.next;

}else{

//将要删除的前一个节点指向 要删除节点的后一个节点

prev.next=temp.next;

}

size--;//长度-1

break;

}

prev=temp;//记录上一个节点

temp=temp.next;

count++;

}

}

```

## 测试

```java

public static void main(String[] args) {

SingleLink singleLink = new SingleLink();

singleLink.add(1);

singleLink.add(2);

singleLink.add(3);

System.out.println("删除前=================="+singleLink);

singleLink.removeObject(2);

System.out.println("删除后=================="+singleLink);

}

```

测试效果:

```java

删除前==================[1,2,3]

删除后==================[1,3]

```

## 总结

​ 通过删除节点我们发现,单链表的操作删除时,需要获取被删除的节点的上一个节点,获取上一个节点相对来时比较麻烦。如果使用双链表,那么这个问题就解决了。而且效率要比单链表要高些。下一章,我们来学习下双链表相关的知识,看是如何添加和删除数据的。

0 分享到:
和我们在线交谈!