更新時(shí)間:2018年12月07日11時(shí)28分 來(lái)源:傳智播客 瀏覽次數(shù):
# 數(shù)據(jù)結(jié)構(gòu)-單鏈表的數(shù)據(jù)操作及特性
## 概述
? 上一章中,我們已經(jīng)入門了單鏈表的添加數(shù)據(jù)以及查詢數(shù)據(jù)打印了,那么當(dāng)我們存儲(chǔ)了數(shù)據(jù),要?jiǎng)h除的時(shí)候怎么辦呢?這章,我們來(lái)看看如何刪除數(shù)據(jù)。
![](image\image1.png)
## 根據(jù)數(shù)據(jù)刪除節(jié)點(diǎn)
### 分析
? 根據(jù)數(shù)據(jù)刪除節(jié)點(diǎn),
1. 首先:刪除數(shù)據(jù)分三種情況,1.刪除的節(jié)點(diǎn)是頭節(jié)點(diǎn) 2.刪除的節(jié)點(diǎn)為尾節(jié)點(diǎn) 3.刪除的節(jié)點(diǎn)是中間節(jié)點(diǎn)
2. 其次:需要獲取要?jiǎng)h除的數(shù)據(jù)所對(duì)應(yīng)的節(jié)點(diǎn)以及他的前一個(gè)節(jié)點(diǎn)
3. 刪除節(jié)點(diǎn),需要將鏈表的長(zhǎng)度扣減增加節(jié)點(diǎn)需要長(zhǎng)度增加。
### 實(shí)現(xiàn)
#### 修改增加方法,增加長(zhǎng)度屬性
```java
private transient int size = 0;// 單列表的長(zhǎng)度
/**
* 從尾部添加一個(gè)節(jié)點(diǎn)
*
* @param data
* 要添加的節(jié)點(diǎn)的數(shù)據(jù)
*/
public void add(Object data) {
// 1.構(gòu)建一個(gè)節(jié)點(diǎn)對(duì)象
Node node = new Node(data);
if (head == null) {
// 2.判斷鏈表中是否為空 如果為空 則新增的節(jié)點(diǎn)變成頭節(jié)點(diǎn)
head = node;
} else {
// 3.如果鏈表不為空,則需要查詢到尾部節(jié)點(diǎn)
Node rear = findRearNode();
// 4.向尾部節(jié)點(diǎn)添加一個(gè)節(jié)點(diǎn)
rear.next = node;// rear肯定不為空
}
size++;
}
// 獲取鏈表的長(zhǎng)度
public int size() {
return size;
}
```
#### 編寫刪除的代碼
```java
// 刪除鏈表中的數(shù)據(jù)
public void removeObject(Object data) {
// 賦值為臨時(shí)對(duì)象
Node temp = head;
//記錄要?jiǎng)h除的節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)
Node prev = temp;
if (data != null)
while (temp != null) {
if (data.equals(temp.data) && temp.data.hashCode()==data.hashCode()) {
//如果刪除的是頭節(jié)點(diǎn)
if(temp==head){
head=temp.next;//
//如果刪除的是尾部節(jié)點(diǎn)
}else if(temp.next==null){
prev.next=null;
//如果刪除的是中間節(jié)點(diǎn)
}else{
prev.next=temp.next;
}
size--;
break;
}
prev=temp;
//循環(huán)遍歷
temp=temp.next;
}
}
```
代碼解釋:先查詢數(shù)據(jù)在鏈表中是否有,需要循環(huán)遍歷,當(dāng)數(shù)據(jù)一致 并且hashcode一致時(shí),我們才認(rèn)為這才是兩個(gè)相等的數(shù)據(jù)對(duì)象;接著 獲取前一個(gè)節(jié)點(diǎn)對(duì)象。
## 根據(jù)索引刪除節(jié)點(diǎn)
### 分析
? 根據(jù)索引刪除節(jié)點(diǎn),也就是說(shuō)從第幾個(gè)位置開始刪除,默認(rèn)第一個(gè)位置索引為0 以此類推。
1. 首先:刪除的節(jié)點(diǎn)的索引不能超過(guò)總長(zhǎng)度
2. 其次:刪除的節(jié)點(diǎn) 要先找到對(duì)應(yīng)節(jié)點(diǎn)數(shù)據(jù) 再刪除。
### 實(shí)現(xiàn)
?
```java
/**
* 根據(jù)指定的索引來(lái)刪除鏈表中的數(shù)據(jù)
* @param index
*/
public void removeIndexObject(int index) {
int count=0;
if(index<0 ||index >=size){
System.out.println("越界");
return;
}
Node temp = head;
//記錄前一個(gè)節(jié)點(diǎn)
Node prev = temp;
while (temp != null) {
if(count==index){
if(index==0){//說(shuō)明刪除的是頭節(jié)點(diǎn)
head = temp.next;
}else{
//將要?jiǎng)h除的前一個(gè)節(jié)點(diǎn)指向 要?jiǎng)h除節(jié)點(diǎn)的后一個(gè)節(jié)點(diǎn)
prev.next=temp.next;
}
size--;//長(zhǎng)度-1
break;
}
prev=temp;//記錄上一個(gè)節(jié)點(diǎn)
temp=temp.next;
count++;
}
}
```
## 測(cè)試
```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);
}
```
測(cè)試效果:
```java
刪除前==================[1,2,3]
刪除后==================[1,3]
```
## 總結(jié)
? 通過(guò)刪除節(jié)點(diǎn)我們發(fā)現(xiàn),單鏈表的操作刪除時(shí),需要獲取被刪除的節(jié)點(diǎn)的上一個(gè)節(jié)點(diǎn),獲取上一個(gè)節(jié)點(diǎn)相對(duì)來(lái)時(shí)比較麻煩。如果使用雙鏈表,那么這個(gè)問(wèn)題就解決了。而且效率要比單鏈表要高些。下一章,我們來(lái)學(xué)習(xí)下雙鏈表相關(guān)的知識(shí),看是如何添加和刪除數(shù)據(jù)的。
北京校區(qū)