鏈表
- 1.前言
- 2.定義
- 3.模板設計
- 4.單鏈表
- 4.1概念
- 4.2基本操作
- 4.2.1添加
- 4.2.2洗掉
- 4.2.3修改
- 4.2.4查詢
- 5.雙向鏈表
- 5.1概念
- 5.2基本操作
- 5.2.1添加
- 5.2.2洗掉
- 5.2.3修改
- 5.2.4查詢
- 6.單向回圈鏈表
- 6.1概念
- 6.2基本操作
- 6.2.1添加
- 6.2.2洗掉
- 6.2.3修改
- 6.2.4查詢
- 7.雙向回圈鏈表
- 7.1概念
- 7.2基本操作
- 7.2.1添加
- 7.2.2洗掉
- 7.2.3修改
- 7.2.4查詢
1.前言
前面我們已經學習了陣列,陣列容量一經定義難以改變,同時洗掉和插入元素需要移動大量的資料元素,效率較低,為此,引入了線性表中的鏈式存盤結構,鏈式存盤的資料元素不再具有連續的地址,同時可以根據需要隨時申請和釋放空間,更加靈活高效,但是喪失了隨機訪問的能?,
2.定義
鏈表是一種物理存盤單元上非連續、非順序的存盤結構,資料元素的邏輯順序是通過鏈表中的指標鏈接次序實作的,鏈表由一系列結點(鏈表中每一個元素稱為結點)組成,是一種遞回的資料結構,結點可以在運行時動態生成,每個結點包括兩個部分:一個是存盤資料元素的資料域,另一個是存盤下一個結點地址的指標域,

3.模板設計

設計一個List介面,里面寫一些通用的操作,供其他類實作,創建抽象類AbstractList,繼承List介面,實作一些通用的操作,比如判斷索引是否越界之類的常用操作,
List介面
public interface List<E> {
static final int ELEMENT_NOT_FOUND = -1;
/**
* 清除所有元素
*/
void clear();
/**
* 元素的數量
* @return
*/
int size();
/**
* 是否為空
* @return
*/
boolean isEmpty();
/**
* 是否包含某個元素
* @param element
* @return
*/
boolean contains(E element);
/**
* 添加元素到尾部
* @param element
*/
void add(E element);
/**
* 獲取index位置的元素
* @param index
* @return
*/
E get(int index);
/**
* 設定index位置的元素
* @param index
* @param element
* @return 原來的元素?
*/
E set(int index, E element);
/**
* 在index位置插入一個元素
* @param index
* @param element
*/
void add(int index, E element);
/**
* 洗掉index位置的元素
* @param index
* @return
*/
E remove(int index);
/**
* 查看元素的索引
* @param element
* @return
*/
int indexOf(E element);
}
抽象類AbstractList
public abstract class AbstractList<E> implements List<E> {
/**
* 元素的數量
*/
protected int size;
/**
* 元素的數量
* @return
*/
public int size() {
return size;
}
/**
* 是否為空
* @return
*/
public boolean isEmpty() {
return size == 0;
}
/**
* 是否包含某個元素
* @param element
* @return
*/
public boolean contains(E element) {
return indexOf(element) != ELEMENT_NOT_FOUND;
}
/**
* 添加元素到尾部
* @param element
*/
public void add(E element) {
add(size, element);
}
protected void outOfBounds(int index) {
throw new IndexOutOfBoundsException("Index:" + index + ", Size:" + size);
}
protected void rangeCheck(int index) {
if (index < 0 || index >= size) {
outOfBounds(index);
}
}
protected void rangeCheckForAdd(int index) {
if (index < 0 || index > size) {
outOfBounds(index);
}
}
}
4.單鏈表
4.1概念
顧名思義,單鏈表就是表示資料結點只有一個指標域,同時在單鏈表具體功能的實作中,為了讓代碼更加精簡,統一所有節點的處理邏輯,可以在最前面增加一個虛擬的頭結點的輔助結點(不存盤資料),同時,由于單鏈表的表頭元素中沒有前驅,所以創建一個指向表頭結點的指標,來存盤表頭結點的地址,稱為單鏈表的頭指標變數,即下圖中的first,

4.2基本操作
為了更好的實作下面的增刪改查操作,我們首先首先用一個靜態內部類來定義結點的抽象資料型別
private static class Node<E> {
E element;
Node<E> next;
public Node(E element, Node<E> next) {
this.element = element;
this.next = next;
}
}
一個 Node 物件含有兩個實體變數,型別分別為 E(引數型別) 和 Node,其中next用來指向下一個鏈表,element用來存盤一個結點的資料,我們會在需要使用 Node 類的類中定義它并將它標記為 private,因為它不是為用例準備的,
然后創建一個first指標,指向頭結點,
private Node<E> first;
我們再寫一個node方法,用來獲取index位置對應的節點物件,首先檢查index值是否合理,如果合理,創建結點node指向頭結點,進行index次回圈,每次讓結點node指向下一個結點,回圈結束回傳node,
/**
* 獲取index位置對應的節點物件
* @param index
* @return
*/
private Node<E> node(int index) {
rangeCheck(index);
Node<E> node = first.next;
for (int i = 0; i < index; i++) {
node = node.next;
}
return node;
}
同時重寫indexOf方法,用來獲取元素的位置,具體操作與上面類似
@Override
public int indexOf(E element) {
if (element == null) {
Node<E> node = first;
for (int i = 0; i < size; i++) {
if (node.element == null) return i;
node = node.next;
}
} else {
Node<E> node = first;
for (int i = 0; i < size; i++) {
if (element.equals(node.element)) return i;
node = node.next;
}
}
return ELEMENT_NOT_FOUND;
}
4.2.1添加

如果要在index=0位置處插入元素,只需要讓虛擬頭結點的next指向新插入的結點,新插入結點的next指向原先0位置的結點,

如果在其他合理位置插入,只需要找到前一個結點,讓他的next指向新插入的結點,新插入結點的next指向原先位置的結點,
@Override
public void add(int index, E element) {
rangeCheckForAdd(index);
Node<E> prev = index == 0 ? first : node(index - 1);
prev.next = new Node<>(element, prev.next);
size++;
}
4.2.2洗掉

如果洗掉index=0位置處的結點,只需要讓虛擬頭結點的next指向index=1處的結點,在Java中,0位置指向1位置的next不用設定為null,曾經的結點物件沒有其他結點指向它,變成了"孤兒",Java 的記憶體管理系統最終將回收它所占用的記憶體,

如果洗掉其他位置的結點,只需要找到待洗掉元素的前一個結點,讓它指向待洗掉元素的下一個結點,
@Override
public E remove(int index) {
rangeCheck(index);
Node<E> prev = index == 0 ? first : node(index - 1);
Node<E> node = prev.next;
prev.next = node.next;
size--;
return node.element;
}
4.2.3修改
@Override
public E set(int index, E element) {
Node<E> node = node(index);
E old = node.element;
node.element = element;
return old;
}
4.2.4查詢
@Override
public E get(int index) {
return node(index).element;
}
5.雙向鏈表
5.1概念

看圖就知道,雙向鏈表與單鏈表的不同之處在于每個結點都增加了一個指向其前驅的指標域,其余不變,同時呢,為了更好的操作,我們再添加一個first指標指向第一個結點,一個last指標指向最后一個結點,
當只有一個元素時

5.2基本操作
與單鏈表的操作類似,創建一個內部類Node
private static class Node<E> {
E element;
//前一結點地址
Node<E> prev;
//后一結點地址
Node<E> next;
public Node(Node<E> prev, E element, Node<E> next) {
this.prev = prev;
this.element = element;
this.next = next;
}
}
然后創建first和last指標分別指向第一個結點和最后一個結點,
private Node<E> first;
private Node<E> last;
5.2.1添加

如果原先鏈表不為空,我們在鏈表最后添加元素,
- 我們先拿到原先的last,就命名為oldLast
- 讓新添加的node前驅結點指向oldLast,后驅結點指向null,然后讓last指向新添加的結點,
- 讓oldLast的next指向新添加的結點,
當鏈表為空時,添加第一個元素,即oldLast為null,只需要first=last

同樣鏈表有其他結點,我們在非首尾位置添加結點,
- 通過
node(index)獲取到原先位置的結點,命名為next, - 通過
next.prev獲取原先node位置的前驅元素prev,讓新添加的node元素的前驅結點指向prev,后驅結點指向next, - 通過
next.prev = node指向新添加的元素,最后通過prev.next = node讓前驅元素指向新添加的元素node,
當添加在0位置的元素時,前面獲取的prev元素為null,只需要讓first指向新添加的node
@Override
public void add(int index, E element) {
rangeCheckForAdd(index);
if (index == size) { // 往最后面添加元素,可能沒有元素
Node<E> oldLast = last;
last = new Node<>(oldLast, element, null);
if (oldLast == null) { // 這是鏈表添加的第一個元素
first = last;
} else {
oldLast.next = last;
}
} else {
Node<E> next = node(index);
Node<E> prev = next.prev;
Node<E> node = new Node<>(prev, element, next);
next.prev = node;
if (prev == null) { // index == 0
first = node;
} else {
prev.next = node;
}
}
size++;
}
5.2.2洗掉

當鏈表結構如上圖時,洗掉最后一個元素
- 通過
node(3)獲取要洗掉的元素node,然后分別獲取到它的前驅結點prev和后繼結點next, - 通過
prev.next = next使前驅結點指向null - 最后讓
last指向prev

當洗掉第一個元素時
- 通過
node(0)獲取要洗掉的元素node,然后分別獲取到它的前驅結點prev和后繼結點next, - 發現
prev=null,則直接first=next,指向待刪元素的下一個結點 - 最后
next.prev = prev,其實這里的prev==null

當洗掉非首尾結點時
- 通過
node(index)獲取要洗掉的元素node,然后分別獲取到它的前驅結點prev和后繼結點next, - 通過
prev.next = next使前驅結點指向被刪元素的后一個結點 - 最后
next.prev = prev,使被刪元素的后一個結點next指向被刪元素的前一個結點perv
@Override
public E remove(int index) {
rangeCheck(index);
Node<E> node = node(index);
Node<E> prev = node.prev;
Node<E> next = node.next;
if (prev == null) { // index == 0
first = next;
} else {
prev.next = next;
}
if (next == null) { // index == size - 1
last = prev;
} else {
next.prev = prev;
}
size--;
return node.element;
}
5.2.3修改
@Override
public E set(int index, E element) {
Node<E> node = node(index);
E old = node.element;
node.element = element;
return old;
}
5.2.4查詢
@Override
public E get(int index) {
return node(index).element;
}
6.單向回圈鏈表
6.1概念
為了某些操作實作方便,常將單鏈表中的最后一個結點的指標域指向頭結點,這樣就形成了首尾相連的結構,稱為回圈單鏈表,

當只有一個結點時,結點的next指向自己,如下圖

6.2基本操作
先創建一個內部類Node
private static class Node<E> {
E element;
Node<E> next;
public Node(E element, Node<E> next) {
this.element = element;
this.next = next;
}
}
然后創建first指向第一個結點,
private Node<E> first;
6.2.1添加

當添加元素的位置為0時
- 我們先讓待插入結點
newFirst的next指向原先0號位置的結點 - 如果此時的鏈表不為空,即
size!=0,通過node(index-1)獲取最后一個結點,如果此時鏈表為空,最后一個結點就是它自己,讓它的next指向它自己,然后讓最后一個結點的next指向newFirst - 此時的first還指向原先的第一個結點,最后將它的指標引向newFirst,即
first = newFirst

當添加的元素位置不為0時
- 首先獲取待添加位置的前一個元素,比如添加新結點到三號位置,先通過
node(index-1)獲取前一個元素prev - 讓prev的next指向新插入的結點,讓新插入結點的next指向原先位置的元素
@Override
public void add(int index, E element) {
rangeCheckForAdd(index);
if (index == 0) {
Node<E> newFirst = new Node<>(element, first);
// 拿到最后一個節點
Node<E> last = (size == 0) ? newFirst : node(size - 1);
last.next = newFirst;
first = newFirst;
} else {
Node<E> prev = node(index - 1);
prev.next = new Node<>(element, prev.next);
}
size++;
}
6.2.2洗掉

當洗掉元素為第一個時
- 首先判斷這個鏈表是不是只含這一個元素,如果只含這一個,只需要first=null,沒有指標引向它,它就會被回收,也就達到了洗掉的目的,
- 如果還有其它的元素,首先將first指向原先一號位置的元素,即
first = first.next,然后通過node(size - 1)獲取最后一個元素,使其指向原先的一號位置元素,即last.next = first

當洗掉元素不是第一個時
1.通過node(index - 1)獲取待洗掉元素的前一個結點prev,只需要讓前一個結點的next指向待洗掉元素的的next,即prev.next = prev.next.next
@Override
public E remove(int index) {
rangeCheck(index);
Node<E> node = first;
if (index == 0) {
if (size == 1) {
first = null;
} else {
Node<E> last = node(size - 1);
first = first.next;
last.next = first;
}
} else {
Node<E> prev = node(index - 1);
node = prev.next;
prev.next = node.next;
}
size--;
return node.element;
}
6.2.3修改
@Override
public E set(int index, E element) {
Node<E> node = node(index);
E old = node.element;
node.element = element;
return old;
}
6.2.4查詢
/**
* 獲取index位置對應的節點物件
* @param index
* @return
*/
private Node<E> node(int index) {
rangeCheck(index);
Node<E> node = first;
for (int i = 0; i < index; i++) {
node = node.next;
}
return node;
}
@Override
public E get(int index) {
return node(index).element;
}
7.雙向回圈鏈表
7.1概念

雙向回圈鏈表的節點不僅包含指向下一個節點的指標(next),還包含指向前一個節點的指標(prev),并且有回圈鏈表的特點,最后一個結點的next指向第一個結點,
當鏈表只有一個元素時:

7.2基本操作
與單鏈表的操作類似,創建一個內部類Node
private static class Node<E> {
E element;
Node<E> prev;
Node<E> next;
public Node(Node<E> prev, E element, Node<E> next) {
this.prev = prev;
this.element = element;
this.next = next;
}
}
然后創建first和last指標分別指向第一個結點和最后一個結點,
private Node<E> first;
private Node<E> last;
7.2.1添加


@Override
public void add(int index, E element) {
rangeCheckForAdd(index);
// size == 0
// index == 0
if (index == size) { // 往最后面添加元素
Node<E> oldLast = last;
last = new Node<>(oldLast, element, first);
if (oldLast == null) { // 這是鏈表添加的第一個元素
first = last;
first.next = first;
first.prev = first;
} else {
oldLast.next = last;
first.prev = last;
}
} else {
Node<E> next = node(index);
Node<E> prev = next.prev;
Node<E> node = new Node<>(prev, element, next);
next.prev = node;
prev.next = node;
if (next == first) { // index == 0
first = node;
}
}
size++;
}
7.2.2洗掉

public E remove(int index) {
rangeCheck(index);
Node<E> node = node(index);
if (size == 1) {
first = null;
last = null;
} else {
Node<E> prev = node.prev;
Node<E> next = node.next;
prev.next = next;
next.prev = prev;
if (node == first) { // index == 0
first = next;
}
if (node == last) { // index == size - 1
last = prev;
}
}
size--;
return node.element;
}
7.2.3修改
@Override
public E set(int index, E element) {
Node<E> node = node(index);
E old = node.element;
node.element = element;
return old;
}
7.2.4查詢
/**
* 獲取index位置對應的節點物件
* @param index
* @return
*/
private Node<E> node(int index) {
rangeCheck(index);
if (index < (size >> 1)) {
Node<E> node = first;
for (int i = 0; i < index; i++) {
node = node.next;
}
return node;
} else {
Node<E> node = last;
for (int i = size - 1; i > index; i--) {
node = node.prev;
}
return node;
}
}
@Override
public E get(int index) {
return node(index).element;
}
轉載請註明出處,本文鏈接:https://www.uj5u.com/yidong/160863.html
標籤:其他
上一篇:CTF ics-04
