Abstract Data Type (ADT) in C/C++: Sorted Linked List

C/C++:
I won’t explain the source code below. Either you understand it or you don’t understand it.
My GNU C++ Compiler under Ubuntu does understand the source code, too. 😉
The code is written for C++, but you can use the code for C as well.

Header file ‚my_list.h‘:
#ifndef MY_LIST_H
#define MY_LIST_H
struct node
{
  int data;
  node *next;
};
node *insert_element_in_ascending_order(node *mylist, int data);
node *insert_element_in_descending_order(node *mylist, int data);
void delete_mylist(node *mylist);
void write_mylist(FILE *textfile, node *mylist);
#endif


CPP file ‚my_list.cpp‘:                // replace ‚my_list.cpp‘ by ‚my_list.c‘ for a C program
#include <iostream>               // remove this line if it shall be a C program
#include <cstdio>                 // replace ‚cstdio‘ by ’stdio.h‘ if it shall be a C program
#include <cstdlib>                // replace ‚cstdlib‘ by ’stdlib.h‘ if it shall be a C program
#include „my_list.h“

using namespace std;              // remove this line if it shall be a C program

node *insert_element_in_ascending_order(node *mylist, int data)
{
  node *element = 0;             // replace ‚0‘ by ‚NULL‘ if it shall be a C program
  node *newelement = 0;          // replace ‚0‘ by ‚NULL‘ if it shall be a C program
  node *before = 0;              // replace ‚0‘ by ‚NULL‘ if it shall be a C program
  if (mylist == 0)               // replace ‚0‘ by ‚NULL‘ if it shall be a C program
  {
    // create a new list if it doesn’t exist
    mylist
= new node;
    mylist->data = data;
    mylist->next
= 0;
            // replace ‚0‘ by ‚NULL‘ if it shall be a C program
  }
  else
  {
    // insert at the end of the list
    element = mylist;
    while (element->next != 0)   // replace ‚0‘ by ‚NULL‘ if it shall be a C program
      element = element->next;
    if (element->data < data)
 
    {
      newelement = new node;
      newelement->data = data;
      newelement->next
= 0;      // replace ‚0‘ by ‚NULL‘ if it shall be a C program
      element->next = newelement;
    }
    else
    {
      if (mylist->data > data)
      {
        // insert at the beginning of the list
        newelement = new node;
        newelement->data = data;
        newelement->next
= mylist;
        mylist = newelement;
      }
      else
      {
        // insert somewhere between the beginning and the end of the list (sorted)
        for (element = mylist; element != 0; element = element->next)   // C: repl. ‚0‘ by ‚NULL‘
          if (element->data < data)
            before = element;
        newelement = new node;
        newelement->data = data;
 

        newelement->next = before->next;
        before->next = newelement;
      }
    }
  }
  return mylist;
}

node *insert_element_in_descending_order(node *mylist, int data)
{
  node *element = 0;              // replace ‚0‘ by ‚NULL‘ if it shall be a C program
  node *newelement = 0;           // replace ‚0‘ by ‚NULL‘ if it shall be a C program
  node *before = 0;               // replace ‚0‘ by ‚NULL‘ if it shall be a C program
  if (mylist == 0)                // replace ‚0‘ by ‚NULL‘ if it shall be a C program
  {
    // create a new list if it doesn’t exist
    mylist = new node;
    mylist->data = data;
    mylist->next
= 0;
             // replace ‚0‘ by ‚NULL‘ if it shall be a C program
  }
  else
  {
    // insert at the end of the list
    element = mylist;
    while (element->next != 0)    // replace ‚0‘ by ‚NULL‘ if it shall be a C program
      element = element->next;
    if (element->data > data)
    {
      newelement = new node;
      newelement->data = data;
      newelement->next
= 0;       // replace ‚0‘ by ‚NULL‘ if it shall be a C program
      element->next = newelement;
    }
    else
    {
      if (mylist->data < data)
      {
        // insert at the beginning of the list
        newelement = new node;
        newelement->data = data;
        newelement->next
= mylist;
        mylist = newelement;
      }
      else
      {
        // insert somewhere between the beginning and the end of the list (sorted)
        for (element = mylist; element != 0; element = element->next)   // C: repl. ‚0‘ by ‚NULL‘
          if (element->data > data)
            before = element;
        newelement = new node;
        newelement->data = data;
        newelement->next
= before->next;
        before->next = newelement;
      }
    }
  }
  return mylist;
}

void delete_mylist(node *mylist)
{
  node *temp = 0;                // replace ‚0‘ by ‚NULL‘ if it shall be a C program
  while (mylist != 0)            // replace ‚0‘ by ‚NULL‘ if it shall be a C program
  {
    temp = mylist->next;
    delete mylist;
    mylist = 0;                  // replace ‚0‘ by ‚NULL‘ if it shall be a C program
    mylist = temp;
  }
}

void write_mylist(FILE *textfile, node *mylist)
{
  int i = 0;
  node *element = 0;             // replace ‚0‘ by ‚NULL‘ if it shall be a C program
  fprintf(textfile, „Output:\n\n“);
  for (element = mylist; element != 0; element = element->next)   // C: replace ‚0‘ by ‚NULL‘
    fprintf(textfile, „%8d\t%8d\n“, ++i, element->data);
}

Example:
#include <iostream>              // remove this line if it shall be a C program
#include <cstdio>                // replace ‚cstdio‘ by ’stdio.h‘ if it shall be a C program
#include <cstdlib>               // replace ‚cstdlib‘ by ’stdlib.h‘ if it shall be a C program
#include „my_list.h“

using namespace std;             // remove this line if it shall be a C program

int main(void)
{
  struct node *mylist = 0;       // replace ‚0‘ by ‚NULL‘ if it shall be a C program
  int dataarray[5] = {15, 3, 1, 20, 7};
  for (int i = 0; i < 5; i++)
    mylist = insert_element_in_ascending_order(mylist, dataarray[i]);
  write_mylist(stdout, mylist);
  delete_mylist(mylist);

}

The brown parts should be easy to memorize because the parts are equal.
The
violet parts show only the used functions of the Sorted Linked List.

The difference between the functions
insert_element_in_ascending_order(…) and insert_element_in_descending_order(…) is that the three red<‚ and ‚>signs change their direction. That’s all.

This program uses words like ‚data‘ and ‚before‘. You should visit one of the following pages here:
Official Webpage of Brent Spiner
Official MySpace page of Brent Spiner
Official Twitter page of Brent Spiner

Many thanks!

Von meinem alten Blog übernommen: http://temporaer-byte2702.blogspot.com/2010/11/abstract-data-type-in-cc-sorted-linked.html