昨天講了單向跟雙向鏈結，今天來講最後一個!!環狀鏈結ლ(́◕◞౪◟◕‵ლ)
還有講一些Linked List 基本操作的pseudo code

環狀鏈結(Circular Linked List)

特性:

• 將單向鏈結的最後一個節點的pointer，指向第一個節點
• 不論從何點開始均可以拜訪所有Nodes(單向鏈結必須從頭開始)
• 回收整條鏈結串列空間的Time=O(1)

Linked List 基本操作

Length 求串列長度(or Node數)

Singly Linked List

Lengths(S:Singly Linked List){
    P=S;
    count=0;
    while(P!=Null)do{
        count++;
        P=P➝link;
    }
    return count;
}

Time=O(n)

Circular Linked List

Lengths(C:Circular Linked List){
    if(C==Null)then return 0;
    else{
        P=C;
        count=0;
        repeat{
            count++;
            P=P➝link;
        }until(P==C)
        return count;
    }
}

Time=O(n)

連接兩條環狀鏈結A、B成為一條Circular Linked List:C

Concatenate(A,B,C:Circular Linked List){
    C=Null;
    if(A!=Null and B==Null) then C==A;
    else if(A==Null and B!=Null) then C==B;
    else if(A!=Null and B!=Null) then{
        ① P = A➝link;
        ②A➝link = B➝link;
        ③B➝link = P;
        ④C=P;
    }
    return C;
}

Time=O(1)

Invert a Singly Linked List)

(圖)

將link的方向改變(ﾉ◕ヮ◕)ﾉ*:･ﾟ✧

Invert(s:Singly Linked List){
    q=Null;
    p=s;
    while(p!=Null) do {
        r=q;
        q=p;
        p=p➝link;
        (q➝link)➝r;
    }
    s=q;
}