ソートされた二重リンクリストを実装するC++プログラム

データ構造では、リンクリストはデータ要素の線形コレクションです。リストの各要素またはノードは、データと次のノードへの参照の2つの項目で構成されます。最後のノードにはnullへの参照があります。リンクリストへのエントリポイントは、リストの先頭と呼ばれます。

二重リンクリストは、ノードと呼ばれる順次リンクされたレコードのセットで構成されます。各ノードには3つのフィールドが含まれています。1つのデータフィールドと2つのリンクフィールドです。ノードのシーケンスフィールドの前のノードと次のノードへの参照。

並べ替えられた二重リンクリストの場合、並べ替えられたデータフィールドの値に従って、リンクリストは並べ替えられたままになります。

アルゴリズム

Begin
   function createnode() to insert node in the list:
      it creates a newnode and inserts the number in the data field of the newnode.
      It checks whether the list is empty or not. If the list is empty put the node as first element and update head.
      Both prev and next pointers will be initialized with NULL.
      If list is not empty, then this newnode will be inserted into the existing linked list in such a way that ultimately the linked list will remain sorted.
      Prev and next pointers will be updated accordingly.
End
Begin
   function display_head() to display the list from the head:
      Initialize c=0.
      Initialize pointer variable with the head node address
      while (c <= i )
         Print the node info
         Update pointer variable
         Increment c.
End
Begin
   function dispslay_tail() to display the list from the tail:
      Initialize m=0.
      Initialize pointer variable with the tail node address
      while (m <= i )
         Print the node info
         Update pointer variable
         Increment m.
End

サンプルコード

#include<iostream>
using namespace std;
struct nod {
   int d;
   nod *n, *p;
}
*p = NULL, *head = NULL, *r = NULL, *np = NULL, *tail = NULL;
int c = 0;
void createnode(int n) {
   np = new nod;
   np->d = n;
   np->n = NULL;
   np->p = NULL;
   if (c == 0) {
      tail = np;
      head = np;
      p = head;
      p->n = head;
      p->p = head;
      c++;
   } else if (c == 1) {
      p = head;
      r = p;
      if (np->d < p->d) {
         np->n = p;
         p->p = np;
         head = np;
         p->n = np;
         np->p = p;
         tail = p;
      } else if (np->d > p->d) {
         p->n = np;
         np->p = p;
         np->n= head;
         p->p = np;
      }
      c++;
   } else {
      p = head;
      r = p;
      if (np->d < p->d) {
         np->n = p;
         p->p = np;
         head = np;
         do {
            p = p->n;
         }
         while (p->n != r);
            tail = p;
            p->n = np;
            np->p = p;
      } else if (np->d > p->d) {
         while (p->n != head && np->d > p->d) {
            r = p;
            p = p->n;
            if (p->n == head && (p->d < np->d)) {
               p->n = np;
               np->p = p;
               np->n = head;
               tail = np;
               head->p = np;
               break;
            } else if (np->d< p->d) {
               r->n= np;
               np->p = r;
               np->n= p;
               p->p= np;
               if (p->n != head) {
                  do {
                     p = p->n;
                  }
                  while (p->n != head);
               }
               tail = p;
               break;
            }
         }
      }
   }
}
void display_head(int i) {
   nod *t = head;
   int c = 0;
   while (c <= i) {
      cout<<t->d<<"\t";
      t = t->n;
      c++;
   }
   cout<<endl;
}
void display_tail(int i) {
   nod *t = tail;
   int m = 0;
   while (m <= i) {
      cout<<t->d<<"\t";
      t = t->p;
      m++;
   }
   cout<<endl;
}
int main() {
   int i = 0, n, a, ch;
   cout<<"enter the no of nodes\n";
   cin>>n;
   while (i < n) {
      cout<<"\nenter value of node\n";
      cin>>a;
      createnode(a);
      i++;
   }
   cout<<"\nsorting Doubly Linked List head first\n";
   display_head(n);
   cout<<"\nsorting Doubly Linked List tail first\n";
   display_tail(n);
}

出力

enter the no of nodes
5
enter value of node
7
enter value of node
4
enter value of node
6
enter value of node
2
enter value of node
1
sorting Doubly Linked List head first
1 2 4 6 7 1
sorting Doubly Linked List tail first
7 6 4 2 1 7