連結串列(Linked List)

文章已搬家，請點擊前往👈

REDIRECT_MODE = 1;

簡介

連結串列(Linked List)是串列(List)的一種，是一種常見的資料結構，利用這個資料結構也能進一步實作出其他的資料結構，例如 堆疊(Stack) 和 佇列(Queue) 等。

它的特性是能夠不使用連續的記憶體空間的情況下，能夠保有並使用一份連續的資料；相對來看，陣列則需要使用連續的記憶體空間。

他的的實作方式是每個節點除了記錄資料之外，還使用額外的指標指向下一個節點，將節點以此方式串連起來形成一個連結串列。

由以上的說明可以知道，使用連結串列的優點如下：

不需使用連續記憶體空間，不需事先指定串列大小。 能夠容易的修改指標，插入或移除節點。

但也有缺點如下：

使用額外的記憶體空間紀錄節點指標。 無法快速索引到某個節點，必須迭代搜索。

此資料結構可以實作的操作變化相當多，這裡實作以下幾種操作：

getFirst：取得第一個節點。 getLast：取得最後一個節點。 addFirst：加入節點在最前面。 addLast：加入節點到最後。 addBefore：加入節點在某節點之前。 addAfter：加入節點在某節點之後。 removeFirst：移除第一個節點。 removeLast：移除最後一個節點。 remove：移除某一個節點。 size：取得串列的數目。

連結串列也有許多種類，這邊實作兩種基本的連結串列版本：

單向連結串列(Singly Linked List)

單向連結串列的每個節點只記錄了下一個節點(或者上一個節點)，而尾端的節點指向空值。如下圖：

插入新節點示意圖

移除節點示意圖

然而我們從上圖中可以看到，刪除節點的時候是刪除指定的節點(node)後面的節點(node.next)，而不是刪除節點本身，在程式介面中不是很直覺，例如remove(node)，結果被刪除的是node.next。

那為什麼不直接刪除指定節點？因為必須要找到被刪除的節點的前一個節點(node.previous)，將他的下一個節點重新指向，而在單向連結串列中沒辦法直接取得上一個節點，除非從頭開始找。

雙向連結串列(Doubly Linked List)

而雙向連結串列則同時記錄了下一個節點和上一個節點，除了尾端節點的下一個節點指向空值外，第一個節點的前一個節點也指向空值。如下圖：

因為多紀錄了上一個節點，所以就能夠解決單向連結串列中所提到的問題。

語法

C#

抽象類別

using System; using System.Collections.Generic; using System.Linq; using System.Text;

namespace LinkedList { abstract class LinkedList { public int Count { get; protected set; } public Node First { get; protected set; } public Node Last { get; protected set; } abstract public void AddFirst(T value); abstract public void AddLast(T value); abstract public void AddBefore(Node node, T value); abstract public void AddAfter(Node node, T value); abstract public void RemoveFirst(); abstract public void RemoveLast(); abstract public void Remove(Node node); }

class Node { public Node Next { get; internal set; } public Node Previous { get; internal set; } public T Value { get; internal set; }

public Node(T value) { Value = value; } } }

單向連結串列

using System; using System.Collections.Generic; using System.Linq; using System.Text;

namespace LinkedList { class SinglyLinkedList : LinkedList { public override void AddFirst(T value) { Node node = new Node (value); if (Count == 0) Last = node; else node.Next = First; First = node; ++Count; }

public override void AddLast(T value) { Node node = new Node (value); if (Count == 0) First = node; else Last.Next = node; Last = node; ++Count; }

public override void AddBefore(Node node, T value) { Node newNode = new Node (value); if (node == First) { First = newNode; } else { Node preNode = FindPreviousNode(node); preNode.Next = newNode; } newNode.Next = node; ++Count; }

public override void AddAfter(Node node, T value) { Node newNode = new Node (value); newNode.Next = node.Next; node.Next = newNode; if (node == Last) { Last = newNode; } ++Count; }

public override void RemoveFirst() { if (Count == 0) throw new IndexOutOfRangeException(); else if (Count == 1) { First = null; Last = null; } else { Node node = First.Next; First.Next = null; First = node; } --Count; }

public override void RemoveLast() { if (Count == 0) throw new IndexOutOfRangeException(); else if (Count == 1) { First = null; Last = null; } else { Node node = FindPreviousNode(Last); node.Next = null; Last = node; } --Count; }

public override void Remove(Node node) { if (node == First) RemoveFirst(); else if (node == Last) RemoveLast(); else { Node preNode = FindPreviousNode(node); if (preNode == null) throw new IndexOutOfRangeException(); preNode.Next = node.Next; node.Next = null; --Count; } }

private Node FindPreviousNode(Node node) { Node preNode = First; while (preNode != null) { if (node == preNode.Next) break; preNode = preNode.Next; } return preNode; } } }

雙向連結串列

using System; using System.Collections.Generic; using System.Linq; using System.Text;

namespace LinkedList { class DoublyLinkedList : LinkedList { public override void AddFirst(T value) { Node node = new Node (value); if (Count == 0) Last = node; else { node.Next = First; First.Previous = node; } First = node; ++Count; }

public override void AddLast(T value) { Node node = new Node (value); if (Count == 0) First = node; else { Last.Next = node; node.Previous = Last; } Last = node; ++Count; }

public override void AddBefore(Node node, T value) { Node newNode = new Node (value); newNode.Previous = node.Previous; node.Previous.Next = newNode; node.Previous = newNode; newNode.Next = node; if (node == First) { First = newNode; } ++Count; }

public override void AddAfter(Node node, T value) { Node newNode = new Node (value); newNode.Next = node.Next; node.Next.Previous = newNode; node.Next = newNode; newNode.Previous = node; if (node == Last) { Last = newNode; } ++Count; }

public override void RemoveFirst() { if (Count == 0) throw new IndexOutOfRangeException(); else if (Count == 1) { First = null; Last = null; } else { Node node = First.Next; First.Next = null; node.Previous = null; First = node; } --Count; }

public override void RemoveLast() { if (Count == 0) throw new IndexOutOfRangeException(); else if (Count == 1) { First = null; Last = null; } else { Node node = Last.Previous; Last.Previous = null; node.Next = null; Last = node; } --Count; }

public override void Remove(Node node) { if (node == First) RemoveFirst(); else if (node == Last) RemoveLast(); else { node.Previous.Next = node.Next; node.Next.Previous = node.Previous; node.Next = null; node.Previous = null; --Count; } } } }

Java

抽象類別

public abstract class LinkedList { protected int count; protected Node first; protected Node last;

public Node getFirst() { return first; } public Node getLast() { return last; } public int size() { return count; } abstract public void addFirst(T value); abstract public void addLast(T value); abstract public void addBefore(Node node, T value); abstract public void addAfter(Node node, T value); abstract public void removeFirst(); abstract public void removeLast(); abstract public void remove(Node node); }

public class Node { private Node previous; private Node next; private T value;

public Node getPrevious() { return previous; } void setPrevious(Node previous) { this.previous = previous; } public Node getNext() { return next; } void setNext(Node next) { this.next = next; } public T getValue() { return value; } void setValue(T value) { this.value = value; }

public Node(T value) { this.value = value; } }

單向連結串列

public class SinglyLinkedList extends LinkedList {

@Override public void addFirst(T value) { // TODO Auto-generated method stub Node node = new Node (value); if (count == 0) last = node; else node.setNext(first); first = node; ++count; }

@Override public void addLast(T value) { // TODO Auto-generated method stub Node node = new Node (value); if (count == 0) first = node; else last.setNext(node); last = node; ++count; }

@Override public void addBefore(Node node, T value) { // TODO Auto-generated method stub Node newNode = new Node (value); if (node == first) { first = newNode; } else { Node preNode = findPreviousNode(node); preNode.setNext(newNode); } newNode.setNext(node); ++count; }

@Override public void addAfter(Node node, T value) { // TODO Auto-generated method stub Node newNode = new Node (value); newNode.setNext(node.getNext()); node.setNext(newNode); if (node == last) { last = newNode; } ++count; }

@Override public void removeFirst() { // TODO Auto-generated method stub if (count == 0) throw new ArrayIndexOutOfBoundsException(); else if (count == 1) { first = null; last = null; } else { Node node = first.getNext(); first.setNext(null); first = node; } --count; }

@Override public void removeLast() { // TODO Auto-generated method stub if (count == 0) throw new ArrayIndexOutOfBoundsException(); else if (count == 1) { first = null; last = null; } else { Node node = findPreviousNode(last); node.setNext(null); last = node; } --count; }

@Override public void remove(Node node) { // TODO Auto-generated method stub if (node == first) removeFirst(); else if (node == last) removeLast(); else { Node preNode = findPreviousNode(node); if (preNode == null) throw new ArrayIndexOutOfBoundsException(); preNode.setNext(node.getNext()); node.setNext(null); --count; } }

private Node findPreviousNode(Node node) { Node preNode = first; while (preNode != null) { if (node == preNode.getNext()) break; preNode = preNode.getNext(); } return preNode; } }

雙向連結串列

public class DoublyLinkedList extends LinkedList {

@Override public void addFirst(T value) { // TODO Auto-generated method stub Node node = new Node (value); if (count == 0) last = node; else { node.setNext(first); first.setPrevious(node); } first = node; ++count; }

@Override public void addLast(T value) { // TODO Auto-generated method stub Node node = new Node (value); if (count == 0) first = node; else { last.setNext(node); node.setPrevious(last); } last = node; ++count; }

@Override public void addBefore(Node node, T value) { // TODO Auto-generated method stub Node newNode = new Node (value); newNode.setPrevious(node.getPrevious()); node.getPrevious().setNext(newNode); node.setPrevious(newNode); newNode.setNext(node); if (node == first) { first = newNode; } ++count; }

@Override public void addAfter(Node node, T value) { // TODO Auto-generated method stub Node newNode = new Node (value); newNode.setNext(node.getNext()); node.getNext().setPrevious(newNode); node.setNext(newNode); newNode.setPrevious(node); if (node == last) { last = newNode; } ++count; }

@Override public void removeFirst() { // TODO Auto-generated method stub if (count == 0) throw new ArrayIndexOutOfBoundsException(); else if (count == 1) { first = null; last = null; } else { Node node = first.getNext(); first.setNext(null); node.setPrevious(null); first = node; } --count; }

@Override public void removeLast() { // TODO Auto-generated method stub if (count == 0) throw new ArrayIndexOutOfBoundsException(); else if (count == 1) { first = null; last = null; } else { Node node = last.getPrevious(); last.setPrevious(null); node.setNext(null); last = node; } --count; }

@Override public void remove(Node node) { // TODO Auto-generated method stub if (node == first) removeFirst(); else if (node == last) removeLast(); else { node.getPrevious().setNext(node.getNext()); node.getNext().setPrevious(node.getPrevious()); node.setNext(null); node.setPrevious(null); --count; } }

}

C++

抽象類別

#ifndef LINKEDLIST_H #define LINKEDLIST_H

#include "Node.h"

template class LinkedList { public: LinkedList() { count = 0; first = 0; last = 0; } ~LinkedList() { if(first != last) delete first; delete last; } int size() { return count; } Node * front() { return first; } Node * back() { return last; } virtual void push_front(T value) = 0; virtual void push_back(T value) = 0; virtual void insert_before(Node * node, T value) = 0; virtual void insert_after(Node * node, T value) = 0; virtual void pop_front() = 0; virtual void pop_back() = 0; virtual void erase(Node * node) = 0; protected: int count; Node * first; Node * last; private: };

#endif // LINKEDLIST_H

#ifndef NODE_H #define NODE_H

template class Node { public: Node(T v) { value = v; previous = 0; next = 0; } ~Node() { if(previous != next) delete previous; delete next; } Node * previous; Node * next; T value; protected: private: };

#endif // NODE_H

單向連結串列

#ifndef SINGLELINKEDLIST_H #define SINGLELINKEDLIST_H

#include #include "LinkedList.h" #include "Node.h"

template class SinglyLinkedList : public LinkedList { public: void push_front(T value) { Node * node = new Node (value); if (LinkedList ::count == 0) LinkedList ::last = node; else node->next = LinkedList ::first; LinkedList ::first = node; ++LinkedList ::count; } void push_back(T value) { Node * node = new Node (value); if (LinkedList ::count == 0) LinkedList ::first = node; else LinkedList ::last->next = node; LinkedList ::last = node; ++LinkedList ::count; } void insert_before(Node * node, T value) { Node * newNode = new Node (value); if (node == LinkedList ::first) { LinkedList ::first = newNode; } else { Node * preNode = find_previous_node(node); preNode->next = newNode; } newNode->next = node; ++LinkedList ::count; } void insert_after(Node * node, T value) { Node * newNode = new Node (value); newNode->next = node->next; node->next = newNode; if (node == LinkedList ::last) { LinkedList ::last = newNode; } ++LinkedList ::count; } void pop_front() { if (LinkedList ::count == 0) throw std::out_of_range ("empty list"); else if (LinkedList ::count == 1) { LinkedList ::first = 0; LinkedList ::last = 0; } else { Node * node = LinkedList ::first->next; LinkedList ::first->next = 0; LinkedList ::first = node; } --LinkedList ::count; } void pop_back() { if (LinkedList ::count == 0) throw std::out_of_range ("empty list"); else if (LinkedList ::count == 1) { LinkedList ::first = 0; LinkedList ::last = 0; } else { Node * node = find_previous_node(LinkedList ::last); node->next = 0; LinkedList ::last = node; } --LinkedList ::count; } void erase(Node * node) { if (node == LinkedList ::first) pop_front(); else if (node == LinkedList ::last) pop_back(); else { Node * preNode = find_previous_node(node); if (preNode == 0) throw std::out_of_range ("node not in list"); preNode->next = node->next; node->next = 0; --LinkedList ::count; } } protected: private: Node * find_previous_node(Node * node) { Node * preNode = LinkedList ::first; while (preNode != 0) { if (node == preNode->next) break; preNode = preNode->next; } return preNode; } };

#endif // SINGLELINKEDLIST_H

雙向連結串列

#ifndef DOUBLELINKEDLIST_H #define DOUBLELINKEDLIST_H

#include #include "LinkedList.h" #include "Node.h"

template class DoublyLinkedList : public LinkedList { public: void push_front(T value) { Node * node = new Node (value); if (LinkedList ::count == 0) LinkedList ::last = node; else { node->next = LinkedList ::first; LinkedList ::first->previous = node; } LinkedList ::first = node; ++LinkedList ::count; } void push_back(T value) { Node * node = new Node (value); if (LinkedList ::count == 0) LinkedList ::first = node; else { LinkedList ::last->next = node; node->previous = LinkedList ::last; } LinkedList ::last = node; ++LinkedList ::count; } void insert_before(Node * node, T value) { Node * newNode = new Node (value); newNode->previous = node->previous; node->previous->next = newNode; node->previous = newNode; newNode->next = node; if (node == LinkedList ::first) { LinkedList ::first = newNode; } ++LinkedList ::count; } void insert_after(Node * node, T value) { Node * newNode = new Node (value); newNode->next = node->next; node->next->previous = newNode; node->next = newNode; newNode->previous = node; if (node == LinkedList ::last) { LinkedList ::last = newNode; } ++LinkedList ::count; } void pop_front() { if (LinkedList ::count == 0) throw std::out_of_range ("empty list"); else if (LinkedList ::count == 1) { LinkedList ::first = 0; LinkedList ::last = 0; } else { Node * node = LinkedList ::first->next; LinkedList ::first->next = 0; node->previous = 0; LinkedList ::first = node; } --LinkedList ::count; } void pop_back() { if (LinkedList ::count == 0) throw std::out_of_range ("empty list"); else if (LinkedList ::count == 1) { LinkedList ::first = 0; LinkedList ::last = 0; } else {

Node * node = LinkedList ::last->previous; LinkedList ::last->previous = 0; node->next = 0; LinkedList ::last = node; } --LinkedList ::count; } void erase(Node * node) { if (node == LinkedList ::first) pop_front(); else if (node == LinkedList ::last) pop_back(); else { node->previous->next = node->next; node->next->previous = node->previous; node->next = 0; node->previous = 0; --LinkedList ::count; } } protected: private: };

#endif // DOUBLELINKEDLIST_H

下載

VS2010 C#版本

Eclipse Java版本

Code::Blocks C++版本

-->

小殘的程式光廊

提供一些演算法、資料結構、程式題目的整理與說明，PHP和JavaScript的基本教學和一些程式相關問題與解法。

連結串列(Linked List)

參觀人氣

熱門文章

文章分類

電腦程式 (10)

最新文章

文章搜尋

文章精選