公告版位

簡介

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

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

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

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

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

但也有缺點如下:

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

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

  1. getFirst:取得第一個節點。
  2. getLast:取得最後一個節點。
  3. addFirst:加入節點在最前面。
  4. addLast:加入節點到最後。
  5. addBefore:加入節點在某節點之前。
  6. addAfter:加入節點在某節點之後。
  7. removeFirst:移除第一個節點。
  8. removeLast:移除最後一個節點。
  9. remove:移除某一個節點。
  10. size:取得串列的數目。

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

單向連結串列(Singly Linked List)

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

408px-Singly-linked-list_svg  

插入新節點示意圖

未命名  

移除節點示意圖

未命名2   

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

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

雙向連結串列(Doubly Linked List)

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

610px-Doubly-linked-list_svg   

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

語法

C#

抽象類別

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

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

    class Node<T>
    {
        public Node<T> Next { get; internal set; }
        public Node<T> 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<T> : LinkedList<T>
    {
        public override void AddFirst(T value)
        {
            Node<T> node = new Node<T>(value);
            if (Count == 0)
                Last = node;
            else
                node.Next = First;
            First = node;
            ++Count;
        }

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

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

        public override void AddAfter(Node<T> node, T value)
        {
            Node<T> newNode = new Node<T>(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<T> 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<T> node = FindPreviousNode(Last);
                node.Next = null;
                Last = node;
            }
            --Count;
        }

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

        private Node<T> FindPreviousNode(Node<T> node)
        {
            Node<T> 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<T> : LinkedList<T>
    {
        public override void AddFirst(T value)
        {
            Node<T> node = new Node<T>(value);
            if (Count == 0)
                Last = node;
            else
            {
                node.Next = First;
                First.Previous = node;
            }
            First = node;
            ++Count;
        }

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

        public override void AddBefore(Node<T> node, T value)
        {
            Node<T> newNode = new Node<T>(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<T> node, T value)
        {
            Node<T> newNode = new Node<T>(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<T> 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<T> node = Last.Previous;
                Last.Previous = null;
                node.Next = null;
                Last = node;
            }
            --Count;
        }

        public override void Remove(Node<T> 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<T> {
	protected int count;
	protected Node<T> first;
	protected Node<T> last;

	public Node<T> getFirst()
	{
		return first;
	}
	public Node<T> 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<T> node, T value);
    abstract public void addAfter(Node<T> node, T value);
    abstract public void removeFirst();
    abstract public void removeLast();
    abstract public void remove(Node<T> node);
}
public class Node<T>
{
	private Node<T> previous;
	private Node<T> next;
	private T value;

    public Node<T> getPrevious() 
    { 
    	return previous; 
    }
    
    void setPrevious(Node<T> previous) 
    { 
    	this.previous = previous;
    }
    
    public Node<T> getNext() 
    { 
    	return next; 
    }
    
    void setNext(Node<T> 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<T> extends LinkedList<T> {

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

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

	@Override
	public void addAfter(Node<T> node, T value) {
		// TODO Auto-generated method stub
		Node<T> newNode = new Node<T>(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<T> 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<T> node = findPreviousNode(last);
			node.setNext(null);
			last = node;
		}
		--count;
	}

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

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

雙向連結串列

public class DoublyLinkedList<T> extends LinkedList<T> {

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

	@Override
	public void addBefore(Node<T> node, T value) {
		// TODO Auto-generated method stub
        Node<T> newNode = new Node<T>(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<T> node, T value) {
		// TODO Auto-generated method stub
        Node<T> newNode = new Node<T>(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<T> 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<T> node = last.getPrevious();
            last.setPrevious(null);
            node.setNext(null);
            last = node;
        }
        --count;
	}

	@Override
	public void remove(Node<T> 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<typename T>
class LinkedList
{
    public:
        LinkedList()
        {
            count = 0;
            first = 0;
            last = 0;
        }
        ~LinkedList()
        {
            if(first != last)
                delete first;
            delete last;
        }
        int size()
        {
            return count;
        }
        Node<T>* front()
        {
            return first;
        }
        Node<T>* back()
        {
            return last;
        }
        virtual void push_front(T value) = 0;
        virtual void push_back(T value) = 0;
        virtual void insert_before(Node<T>* node, T value) = 0;
        virtual void insert_after(Node<T>* node, T value) = 0;
        virtual void pop_front() = 0;
        virtual void pop_back() = 0;
        virtual void erase(Node<T>* node) = 0;
    protected:
        int count;
        Node<T>* first;
        Node<T>* last;
    private:
};

#endif // LINKEDLIST_H
#ifndef NODE_H
#define NODE_H

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

#endif // NODE_H

單向連結串列

#ifndef SINGLELINKEDLIST_H
#define SINGLELINKEDLIST_H

#include <stdexcept>
#include "LinkedList.h"
#include "Node.h"

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

#endif // SINGLELINKEDLIST_H

雙向連結串列

#ifndef DOUBLELINKEDLIST_H
#define DOUBLELINKEDLIST_H

#include <stdexcept>
#include "LinkedList.h"
#include "Node.h"

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

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

#endif // DOUBLELINKEDLIST_H

下載

VS2010 C#版本

Eclipse Java版本

Code::Blocks C++版本

文章標籤
創作者介紹

小殘的程式光廊

emn178 發表在 痞客邦 PIXNET 留言(2) 人氣()


留言列表 (2)

發表留言
  • C++ 部分單向鏈結要多一行
  • void insert_after(Node<T>* node, T value)//加入新節點到此節點的後面
    {
    Node<T>* newNode = new Node<T>(value);
    newNode->next = node->next;
    node->next = newNode;
    if(node==LinkedList<T>::last){LinkedList<T>::last=newNode;}
    ++LinkedList<T>::count;

    }

    by 常常懶得做作業來這裡抄的同學
  • 已修正

    emn178 於 2017/05/16 22:10 回覆

  • tyuiop789456123
  • 請問要怎麼在main.cpp內 加入insert_before (c++ doublelinked list版本)
  • 假設你檔案為DoublyLinkedList.h, 在main.cpp
    #include "DoublyLinkedList.h"

    emn178 於 2017/05/16 22:17 回覆

找更多相關文章與討論