連結リスト

連結リストの性質

要素の追加と先頭からの要素の削除が一定時間でできます。 k番目の要素にアクセスするにはk回計算が必要になります。

単方向連結リスト

pythonでの実装です。

class Node():
    def __init__(self, d):
        self.data = d
        self.next = None

    def appendToTail(self, d):
        end = Node(d)
        n = self
        while(n.next):
            n = n.next
        n.next = end

def deleteNode(head, d):
    """
    初めに出てきたdを削除する
    """
    n = head
    if(n.data == d):
        return head.next

    while(n.next):
        if(n.next.data == d):
            n.next = n.next.next
            return head
        n = n.next
    return head

nodeの削除を行ってみます。

if __name__ == "__main__":
    node = Node(10)
    for i in range(10):
        node.appendToTail(i%5)
    print("元の単方向連結リスト")
    _ = node
    print("%d" % _.data, end="")
    while(_.next): # nodeがNoneでない間回る。
        _ = _.next
        print(" -> %d"%_.data, end="")

    node = deleteNode(node, 3)
    print("\n初めに出てくる3を削除した")
    _ = node
    print("%d" % _.data, end="")
    while(_.next): # nodeがNoneでない間回る。
        _ = _.next
        print(" -> %d"%_.data, end="")

すると出力は

元の単方向連結リスト
5 -> 0 -> 1 -> 2 -> 3 -> 4 -> 0 -> 1 -> 2 -> 3 -> 4
初めに出てくる3を削除した
5 -> 0 -> 1 -> 2 -> 4 -> 0 -> 1 -> 2 -> 3 -> 4

双方向連結リスト

pythonで実装しました。

前と次が参照できます。

# 双方向連結リスト
class LinkedList():
    def __init__(self, d, n=None, p=None):
        self.data = d
        self.prev = None
        self.next = None
        self.setNext(n)
        self.setPrevious(p)

    def setNext(self, n):
        self.next = n
        if(n != None) and (n.prev != self):
            n.setPrevious(self)

    def setPrevious(self, p):
        self.prev = p
        if(p != None) and (p.next != self):
            p.setNext(self)

実際に連結リストを作成してみます。

if __name__ == "__main__":
    link=None
    for i in range(10):
        link = LinkedList(i, n=None, p=link)
    print("双方向連結リスト"+"-"*30)
    print("初めに戻る")
    _ = link
    print("%d" % _.data, end="")
    while(_.prev): # nodeがNoneでない間回る。
        _ = _.prev
        print(" -> %d"%_.data, end="")
    print()
    print("初めから最後へ")
    print("%d" % _.data, end="")
    while(_.next): # nodeがNoneでない間回る。
        _ = _.next
        print(" -> %d"%_.data, end="")

出力は

双方向連結リスト------------------------------
初めに戻る
9 -> 8 -> 7 -> 6 -> 5 -> 4 -> 3 -> 2 -> 1 -> 0
初めから最後へ
0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9

C++で実装

#include<iostream>
using namespace std;

//双方向
class Node{
public:
    Node* prev;
    Node* next;
    int data;

    Node(int data){
        this->prev = NULL;
        this->next = NULL;
        this->data = data;
    }
    ~Node(){
        cout << "Node DELETED" << endl;
    }
    void setNext(Node* n){
        this->next = n;
        if((n!=NULL)&&(n->prev!=this)){
            n->setPrevious(this);
        }
    }
    void setPrevious(Node* p){
        this->prev = p;
        if((p!=NULL)&&(p->next!=this)){
            p->setNext(this);
        }
    }
};
class LinkedList{
public:
    Node* node;
    int length;

    LinkedList(){
        this->node = NULL;
        this->length = 0;
    }
    ~LinkedList(){
        cout << "list deleted" << endl;
    }
    void setNext(int data){
        Node* n = new Node(data);
        if(this->node==NULL){
            this->node = n;
        }else{
            this->node->setNext(n);
            this->node = n;
        }
        this->length++;
    }
    void setPrevious(int data){
        Node* p = new Node(data);
        if(this->node==NULL){
            this->node = p;
        }else{
            this->node->setPrevious(p);
        }
        this->length++;
    }
    LinkedList* next(){
        if((this->node)&&(this->node->next)){
            this->node = this->node->next;
        }
        return this;
    }
    LinkedList* prev(){
        if((this->node)&&(this->node->prev)){
            this->node = this->node->prev;
        }
        return this;
    }
};

実行したものは以下です。

int main(void){
    LinkedList* list = new LinkedList();
    int i;
    for(i=0; i<10; i++){
        list->setNext(i);
    }
    cout << "前に戻る" << endl;
    while(list->node->data){
        cout << list->node->data << " -> ";
        if(list->node->prev)list->prev();
    }
    list->prev();
    cout << list->node->data << " -> ";
    cout << endl;
    cout << "次に進む" << endl;
    for(i=0; i<list->length; i++){
        cout << list->next()->node->data << " -> ";
    }
    return 0;
}

  > ./a.out
前に戻る
9 -> 8 -> 7 -> 6 -> 5 -> 4 -> 3 -> 2 -> 1 -> 0 ->
次に進む
1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 9 ->