1.鏈表基礎(chǔ)
- 鏈表是數(shù)據(jù)結(jié)構(gòu)中另一種最基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)破花，數(shù)組需要開辟一段連續(xù)的存儲空間渊迁，所以在初始化的時(shí)候需要指定大小跨新，而鏈表并不需要指定大小，只要有足夠的空間都可以不斷地添加元素
- 鏈表適合于增刪比較頻繁的數(shù)據(jù)蛆挫，而數(shù)據(jù)更適用于改動少赃承，查詢操作頻繁的情況，在根據(jù)索引查詢的時(shí)候可以快速定位
- 鏈表不存在存儲空間不足的情況(除物理分配內(nèi)存不足)悴侵，而java中也有由鏈表為底層數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)的數(shù)據(jù)結(jié)構(gòu)瞧剖，支持泛型，即LinkedList(雙向鏈表)
- 根據(jù)鏈表在本文實(shí)現(xiàn)一個單向鏈表可免，模擬LinkedList方法實(shí)現(xiàn)
2.實(shí)現(xiàn)
2.1.定義節(jié)點(diǎn)
- 定義一個私有內(nèi)部類抓于，代表鏈表中的每一個節(jié)點(diǎn)，而每一個結(jié)點(diǎn)中又定義下一個節(jié)點(diǎn)浇借，以替代指針捉撮，同時(shí)使每個節(jié)點(diǎn)連接起來。
public class LinkedList<E> {
private class Node {
public E e;
public Node next;
public Node(E e, Node next) {
this.e = e;
this.next = next;
}
public Node(E e) { this(e, null); }
public Node() { this(null, null); }
@Override
public String toString() { return e.toString(); }
}
//鏈表頭
private Node dummyHead;
private int size;
public LinkedList() {
//虛擬頭節(jié)點(diǎn)指向真正的頭節(jié)點(diǎn)
dummyHead = new Node(null, null);
size = 0;
}
/**
* 獲取鏈表中的元素個數(shù)
* @return ：
*/
public int getSize() { return size; }
/**
* 當(dāng)前鏈表是否為空
* @return ：
*/
public boolean isEmpty() { return size == 0; }
采用設(shè)立一個虛擬頭節(jié)點(diǎn)妇垢，這樣就不要單獨(dú)處理頭節(jié)點(diǎn)巾遭，即初始化時(shí)，初始一個空結(jié)點(diǎn)闯估，而而這個虛擬頭節(jié)點(diǎn)指向存儲的第一個非空結(jié)點(diǎn)灼舍。
2.2.添加一個新節(jié)點(diǎn)
- 新添一個節(jié)點(diǎn)，需要找到新添節(jié)點(diǎn)位置的前一個節(jié)點(diǎn)涨薪，使前一個節(jié)點(diǎn)的指針指向新添加的節(jié)點(diǎn)片仿，而前一個節(jié)點(diǎn)原來指向的節(jié)點(diǎn)，變成新添加節(jié)點(diǎn)指向的節(jié)點(diǎn)
/**
* 在鏈表的index(0-based)位置添加新元素e
* @param index ：插入鏈表新元素的索引位置
*/
public void add(int index, E e) {
if (index < 0 || index > size) {
throw new IllegalArgumentException("Add failed. Illegal index");
}
//代表待添加節(jié)點(diǎn)索引的上一個節(jié)點(diǎn)尤辱，初始指向虛擬頭節(jié)點(diǎn)
Node prev = dummyHead;
//找到要插入位置的上一個元素(前結(jié)點(diǎn))
for (int i = 0; i < index; i++) {
prev = prev.next;
}
//將前結(jié)點(diǎn)的next結(jié)點(diǎn)當(dāng)作新結(jié)點(diǎn)的next,再將新結(jié)點(diǎn)作為前結(jié)點(diǎn)的next實(shí)現(xiàn)插入
prev.next = new Node(e, prev.next);
size++;
}
/**
* 向鏈表中添加元素：
* 在鏈表頭添加新元素砂豌，新元素索引指向當(dāng)前鏈表頭，當(dāng)前鏈表頭指針指向新添加元素
* @param e ：
*/
public void addFirst(E e) { add(0, e); }
/**
* 在鏈表末尾添加一個新元素e
*/
public void addLast(E e) { add(size, e); }
鏈表添加節(jié)點(diǎn).png
2.3.改和查的方法
/**
* 獲取鏈表的第index(0-based)位置的元素e
* @param index ：獲取鏈表元素的索引位置
* @return ：該索引的元素
*/
public E get(int index) {
if (index < 0 || index > size) {
throw new IllegalArgumentException("Get failed. Illegal index");
}
//從頭元素(頭結(jié)點(diǎn))開始
Node cur = dummyHead.next;
//獲取第index位置結(jié)點(diǎn)
for (int i = 0; i < index; i++) {
cur = cur.next;
}
return cur.e;
}
/**
* 獲取鏈表中第一個元素(頭節(jié)點(diǎn)元素)
* @return ：dummyHead.next.e;
*/
public E getFirst() { return get(0); }
/**
* 獲取鏈表中最后一個位置的元素
* @return ：
*/
public E getLast() { return get(size - 1); }
/**
* 修改鏈表中第index(0-based)位置的元素
* 在鏈表中不是一個常用的操作光督，練習(xí)用
*/
public void set(int index, E e) {
if (index < 0 || index > size) {
throw new IllegalArgumentException("Get failed. Illegal index");
}
//從頭元素(頭結(jié)點(diǎn))開始
Node cur = dummyHead.next;
//獲取第index位置結(jié)點(diǎn)
for (int i = 0; i < index; i++) {
cur = cur.next;
}
cur.e = e;
}
/**
* 該鏈表中是否存在該元素
* @param e ：
* @return ：
*/
public boolean contains(E e) {
Node cur = dummyHead.next;
while (cur != null) {
if (cur.e.equals(e)) {
return true;
}
cur = cur.next;
}
return false;
}
2.4.刪除方法
/**
* 刪除鏈表中index(0-based)位置的元素阳距，并返回該元素：將刪除節(jié)點(diǎn)的next結(jié)點(diǎn)代替成刪除節(jié)點(diǎn)的位置
* @param index ：刪除節(jié)點(diǎn)的索引
* @return ：刪除節(jié)點(diǎn)的元素
*/
public E remove(int index) {
if (index < 0 || index > size) {
throw new IllegalArgumentException("Get failed. Illegal index");
}
//從虛擬頭節(jié)點(diǎn)開始
Node prev = dummyHead;
//獲取第index位置結(jié)點(diǎn)的上一個結(jié)點(diǎn)（前結(jié)點(diǎn)）
for (int i = 0; i < index; i++) {
prev = prev.next;
}
Node deleteNode = prev.next;
prev.next = deleteNode.next;
deleteNode.next = null;
size--;
return deleteNode.e;
}
/**
* 刪除鏈表中第一個元素，并返回元素值
* @return ：
*/
public E removeFirst() { return remove(0); }
/**
* 刪除結(jié)點(diǎn)中最后一個元素结借，并返回元素值
* @return ：
*/
public E removeLast() { return remove(size - 1); }
2.5.重寫toString方法
@Override
public String toString() {
StringBuilder str = new StringBuilder();
Node cur = dummyHead.next;
while (cur != null) {
str.append(cur + "-->");
cur = cur.next;
}
str.append("NULL");
return str.toString();
}
