The Sorted Linked List
A sorted linked list is a linear collection of self-referential
structures, called nodes, connected by pointer links, where the
nodes are kept in sorted order by the values found in a particular data member,
known as the key. A sorted linked list, like a general linked list is accessed
by keeping a pointer to the first node of the list. This pointer to the first
node of a list is typically named head. Subsequent nodes are accessed
via a link pointer member that is stored in each node. Additions of nodes to
a sorted linked list, require that the node is placed in the correct position
to keep the list in order by the key.
The operations on linked lists include :
- creation of a node
- setting data into a node
- adding a node to the list
- deleting a node from the list
- is the list empty
- printing the list
The sorted linked list user interface :
<![CDATA[
/*************************************************\
* Filename: sortedll.h *
* Author: Sue Bogar *
* Date Written: 4/22/98 *
* Date Modified: 11/22/98 *
* Section: 101 *
* EMail: bogar@cs.umbc.edu *
* *
* Description: This header file contains the *
* structure definition for a node type, to be *
* used as the nodes of a linked list, and the *
* function prototypes for the functions defined *
* in sortedll.c, the linked list implementation *
* of the sorted linked list ADT. *
\*************************************************/
#ifndef _sortedll_h
#define _sortedll_h
/****************
* This typedef allows us to call the type
* of a pointer to a node a NODEPTR
*****************/
typedef struct node *NODEPTR;
/*****************
* This struct, typedefed to be of type info, is meant
* to store all the data about cars in a parking lot.
*****************/
typedef struct info
{
char tagNo[8];
char owner[25];
char make[15];
char model[15];
int lot;
} INFO;
/*****************
* The sorted linked list is implemented as
* a structure that has two members, the first to
* to hold data (in this case a struct of type info)
* and the second member is of type NODEPTR which
* holds a pointer to the next node of the list.
* This pointer is known as the a link of the
* linked list.
*****************/
typedef struct node
{
INFO data;
NODEPTR next;
} NODE;
/*****************************************************/
/******************
* CreateNode mallocs the space needed to
* hold a struct of type node, initializes
* the members, and returns a pointer to
* the new node.
******************/
NODEPTR CreateNode (void);
/******************
* SetData places the values
* found in the info structure
* passed to it into the
* node pointed to by the NODEPTR it
* receives as an argument.
******************/
void SetData (NODEPTR temp, INFO new);
/******************
* Insert takes a pointer to a NODEPTR, the
* address of head, and a NODEPTR, temp, as
* arguments. temp is a pointer to the
* node to be inserted. The node is then
* inserted into the list at the appropriate
* place to maintain the list as a sorted list.
******************/
void Insert (NODEPTR* headPtr, NODEPTR temp);
/******************
* Delete takes a pointer to a NODEPTR as its
* first argument, which is the address of head.
* Its second argument is a struct of type info,
* which contains the license plate tag number to
* be removed. The third argument is the string
* in which to store a message. This function
* traverses the list until the node containing the
* target tagNo is found. That node is then deleted
* from the list and a message returned stating that
* fact. If the target tagNo is not in the list and
* a message is returned that it was not found.
******************/
int Delete (NODEPTR* headPtr, char* target);
/******************
* IsEmpty takes a NODEPTR as its first
* argument, which is a pointer to the
* first node in the list, commonly
* known as head. It determines whether the
* list is empty or not and returns 1 (true)
* if the list is empty and 0 (false) if it
* is not empty.
******************/
int IsEmpty (NODEPTR head);
/******************
* PrintList takes a NODEPTR as an argument
* which is a pointer to the first node in
* the list, commonly known as head.
* he list is traversed and the values
* of each of the data members of each node are
* printed.
******************/
void PrintList (NODEPTR head);
#endif
]]>