1.鏈表
鏈表不同于順序表，順序表底層采用數(shù)組作為存儲容器，需要分配一塊連續(xù)且完整的內(nèi)存空間進(jìn)行使用，而鏈表則不需要，它通過一個指針來連接各個分散的結(jié)點(diǎn)，形成了一個鏈狀的結(jié)構(gòu)，每個結(jié)點(diǎn)存放一個元素，以及一個指向下一個結(jié)點(diǎn)的指針，通過這樣一個一個相連，最后形成了鏈表。它不需要申請連續(xù)的空間，只需要按照順序連接即可，雖然物理上可能不相鄰，但是在邏輯上依然是每個元素相鄰存放的，這樣的結(jié)構(gòu)叫做鏈表（單鏈表）。
鏈表分為帶頭結(jié)點(diǎn)的鏈表和不帶頭結(jié)點(diǎn)的鏈表，戴頭結(jié)點(diǎn)的鏈表就是會有一個頭結(jié)點(diǎn)指向后續(xù)的整個鏈表，但是頭結(jié)點(diǎn)不存放數(shù)據(jù)
而不帶頭結(jié)點(diǎn)的鏈表就像上面那樣，第一個節(jié)點(diǎn)就是存放數(shù)據(jù)的結(jié)點(diǎn)，一般設(shè)計(jì)鏈表都會采用帶頭結(jié)點(diǎn)的結(jié)構(gòu)，因?yàn)椴僮鞲臃奖恪?/p>
我們來嘗試定義一下：
public class LinkedList<E> {
//鏈表的頭結(jié)點(diǎn)，用于連接之后的所有結(jié)點(diǎn)
private final Node<E> head = new Node<>(null);
private int size = 0; //當(dāng)前的元素?cái)?shù)量還是要存一下，方便后面操作
private static class Node<E> { //結(jié)點(diǎn)類，僅供內(nèi)部使用
E element; //每個結(jié)點(diǎn)都存放元素
Node<E> next; //以及指向下一個結(jié)點(diǎn)的引用
public Node(E element) {
this.element = element;
}
}
}
1.1插入
鏈表的插入該怎么做：可以先修改新插入的結(jié)點(diǎn)的后繼結(jié)點(diǎn)（也就是下一個結(jié)點(diǎn)）指向，指向原本在這個位置的結(jié)點(diǎn)，接著我們可以將前驅(qū)結(jié)點(diǎn)（也就是上一個結(jié)點(diǎn)）的后繼結(jié)點(diǎn)指向修改為我們新插入的結(jié)點(diǎn)，這樣，我們就成功插入了一個新的結(jié)點(diǎn)，現(xiàn)在新插入的結(jié)點(diǎn)到達(dá)了原本的第二個位置上
public void add(E element, int index){
Node<E> prev = head; //先找到對應(yīng)位置的前驅(qū)結(jié)點(diǎn)
for (int i = 0; i < index; i++)
prev = prev.next;
Node<E> node = new Node<>(element); //創(chuàng)建新的結(jié)點(diǎn)
node.next = prev.next; //先讓新的節(jié)點(diǎn)指向原本在這個位置上的結(jié)點(diǎn)
prev.next = node; //然后讓前驅(qū)結(jié)點(diǎn)指向當(dāng)前結(jié)點(diǎn)
size++; //完事之后一樣的，更新size
}
我們來重寫一下toString方法看看能否正常插入：
@Override
public String toString() {
StringBuilder builder = new StringBuilder();
Node<E> node = head.next; //從第一個結(jié)點(diǎn)開始，一個一個遍歷，遍歷一個就拼接到字符串上去
while (node != null) {
builder.append(node.element).append(" ");
node = node.next;
}
return builder.toString();
}
- 考慮插入位置是否合法：
public void add(E element, int index){
if(index < 0 || index > size)
throw new IndexOutOfBoundsException("插入位置非法，合法的插入位置為：0 ~ "+size);
Node<E> prev = head;
for (int i = 0; i < index; i++)
prev = prev.next;
Node<E> node = new Node<>(element);
node.next = prev.next;
prev.next = node;
size++;
}
1.2刪除
插入操作完成之后，我們接著來看刪除操作，那么我們?nèi)绾螌?shí)現(xiàn)刪除操作呢？實(shí)際上也會更簡單一些，我們可以直接將待刪除節(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)指向修改為待刪除節(jié)點(diǎn)的下一個
這樣，在邏輯上來說，待刪除結(jié)點(diǎn)其實(shí)已經(jīng)不在鏈表中了，所以我們只需要釋放掉待刪除結(jié)點(diǎn)占用的內(nèi)存空間就行了
public E remove(int index){
if(index < 0 || index > size - 1) //同樣的，先判斷位置是否合法
throw new IndexOutOfBoundsException("刪除位置非法，合法的刪除位置為：0 ~ "+(size - 1));
Node<E> prev = head;
for (int i = 0; i < index; i++) //同樣需要先找到前驅(qū)結(jié)點(diǎn)
prev = prev.next;
E e = prev.next.element; //先把待刪除結(jié)點(diǎn)存放的元素取出來
prev.next = prev.next.next; //可以刪了
size--; //記得size--
return e;
}
這樣，我們就成功完成了鏈表的刪除操作。
- 獲取對應(yīng)位置上的元素：
public E get(int index){
if(index < 0 || index > size - 1)
throw new IndexOutOfBoundsException("非法的位置，合法的位置為：0 ~ "+(size - 1));
Node<E> node = head;
while (index-- >= 0) //這里直接讓index減到-1為止
node = node.next;
return node.element;
}
public int size(){
return size;
}
- 什么情況下使用順序表，什么情況下使用鏈表呢？
- 通過分析順序表和鏈表的特性我們不難發(fā)現(xiàn)，鏈表在隨機(jī)訪問元素時，需要通過遍歷來完成，而順序表則利用數(shù)組的特性直接訪問得到，所以，當(dāng)我們讀取數(shù)據(jù)多于插入或是刪除數(shù)據(jù)的情況下時，使用順序表會更好。
- 而順序表在插入元素時就顯得有些雞肋了，因?yàn)樾枰苿雍罄m(xù)元素，整個移動操作會浪費(fèi)時間，而鏈表則不需要，只需要修改結(jié)點(diǎn) 指向即可完成插入，所以在頻繁出現(xiàn)插入或刪除的情況下，使用鏈表會更好。
雖然單鏈表使用起來也比較方便，不過有一個問題就是，如果我們想要操作某一個結(jié)點(diǎn)，比如刪除或是插入，那么由于單鏈表的性質(zhì)，我們只能先去找到它的前驅(qū)結(jié)點(diǎn)，才能進(jìn)行。為了解決這種查找前驅(qū)結(jié)點(diǎn)非常麻煩的問題，我們可以讓結(jié)點(diǎn)不僅保存指向后續(xù)結(jié)點(diǎn)的指針，同時也保存指向前驅(qū)結(jié)點(diǎn)的指針
這樣我們無論在哪個結(jié)點(diǎn)，都能夠快速找到對應(yīng)的前驅(qū)結(jié)點(diǎn)，就很方便了，這樣的鏈表我們成為雙向鏈表（雙鏈表）
2.棧
棧（也叫堆棧，Stack）是一種特殊的線性表，它只能在在表尾進(jìn)行插入和刪除操作
底部稱為棧底，頂部稱為棧頂，所有的操作只能在棧頂進(jìn)行，也就是說，被壓在下方的元素，只能等待其上方的元素出棧之后才能取出，就像我們往箱子里里面放的書一樣，因?yàn)橹挥幸粋€口取出里面的物品，所以被壓在下面的書只能等上面的書被拿出來之后才能取出，這就是棧的思想，它是一種先進(jìn)后出的數(shù)據(jù)結(jié)構(gòu)（FILO，F(xiàn)irst In, Last Out）
實(shí)現(xiàn)棧也是非常簡單的，可以基于我們前面的順序表或是鏈表，這里我們需要實(shí)現(xiàn)兩個新的操作：
- pop：出棧操作，從棧頂取出一個元素。
- push：入棧操作，向棧中壓入一個新的元素。
?？梢允褂庙樞虮韺?shí)現(xiàn)，也可以使用鏈表實(shí)現(xiàn)
2.1入棧
當(dāng)有新的元素入棧，只需要在鏈表頭部插入新的結(jié)點(diǎn)即可，我們來嘗試編寫一下：
public class LinkedStack<E> {
private final Node<E> head = new Node<>(null); //大體內(nèi)容跟鏈表類似
private static class Node<E> {
E element;
Node<E> next;
public Node(E element) {
this.element = element;
}
}
}
入棧操作：
public void push(E element){
Node<E> node = new Node<>(element); //直接創(chuàng)建新結(jié)點(diǎn)
node.next = head.next; //新結(jié)點(diǎn)的下一個變成原本的棧頂結(jié)點(diǎn)
head.next = node; //頭結(jié)點(diǎn)的下一個改成新的結(jié)點(diǎn)
}
2.2出棧
出棧也是同理，所以我們只需要將第一個元素移除即可：
public E pop(){
if(head.next == null) //如果棧已經(jīng)沒有元素了，那么肯定是沒辦法取的
throw new NoSuchElementException("棧為空");
E e = head.next.element; //先把待出棧元素取出來
head.next = head.next.next; //直接讓頭結(jié)點(diǎn)的下一個指向下一個的下一個
return e;
}
3.隊(duì)列
前面我們學(xué)習(xí)了棧，棧中元素只能棧頂出入，它是一種特殊的線性表，同樣的，隊(duì)列（Queue）也是一種特殊的線性表。
就像我們在超市、食堂需要排隊(duì)一樣，我們總是排成一列，先到的人就排在前面，后來的人就排在后面，越前面的人越先完成任務(wù)，這就是隊(duì)列，隊(duì)列有隊(duì)頭和隊(duì)尾
秉承先來后到的原則，隊(duì)列中的元素只能從隊(duì)尾進(jìn)入，只能從隊(duì)首出去，也就是說，入隊(duì)順序?yàn)?、2、3、4，那么出隊(duì)順序也一定是1、2、3、4，所以隊(duì)列是一種先進(jìn)先出（FIFO，F(xiàn)irst In, First Out）的數(shù)據(jù)結(jié)構(gòu)。文章來源：http://www.zghlxwxcb.cn/news/detail-423348.html
隊(duì)列也可以使用鏈表和順序表來實(shí)現(xiàn)，只不過使用鏈表的話就不需要關(guān)心容量之類的問題了，會更加靈活一些文章來源地址http://www.zghlxwxcb.cn/news/detail-423348.html
public class LinkedQueue<E> {
private final Node<E> head = new Node<>(null);
public void offer(E element){ //入隊(duì)操作
Node<E> last = head;
while (last.next != null) //入隊(duì)直接丟到最后一個結(jié)點(diǎn)的屁股后面就行了
last = last.next;
last.next = new Node<>(element);
}
public E poll(){ //出隊(duì)操作
if(head.next == null) //如果隊(duì)列已經(jīng)沒有元素了，那么肯定是沒辦法取的
throw new NoSuchElementException("隊(duì)列為空");
E e = head.next.element;
head.next = head.next.next; //直接從隊(duì)首取出
return e;
}
private static class Node<E> {
E element;
Node<E> next;
public Node(E element) {
this.element = element;
}
}
}
到了這里，關(guān)于計(jì)算機(jī)考研408真題2010年42題的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
