Code Snipet For Doubly Linked List

Danny · #1 18-Sep-2005, 14:39

Thanks for helping me out with the little self imposed project of mine. Just thought I'd submit the completed program.

CPP / C++ / C Code:

/***********************************************************
* Name    : dlink.exe: Code snippets for a doubly linked list
* Date    : September 18, 2005
* Author  : Danny
* License : Do with as you please
* Desc    : Use a doubly linked list to store data.  Can print
*           the list out.  The key added to the
*           struct is a unique identifier for the added element,
*           so deleting and adding elements will still gurantee
*           a unique key for identification purposes.
* Problems: Be sure not to print out a list that has already
*           been deleted!  Also, no user input yet.
* Email   : [email]danny@dannyphillips.com[/email]
* Platform: Microsoft Visual C++ .NET 2003
**********************************************************/

#include <stdio.h>
#include <malloc.h>

struct link {
	int data;
	struct link *next;
	struct link *prev;
	int key;
};

struct link * InitList( void )
{
	struct link *e;

	e = (struct link *)malloc(sizeof(struct link));
	e->data = 0;
	e->next = NULL;
	e->prev = NULL;
	e->key = 0;

	return e;
}

struct link * AddElement( struct link *h )
{
	static int key = 1;
	struct link *tmp;

	if(h->next == NULL && h->prev == NULL) // List is empty
	{
		h->next = (struct link *)malloc(sizeof(struct link));
		h->next->key = key++;
		h->next->next = h;
		h->prev = h->next;
		h->next->prev = h;
		return h;
	}
	else
	{
		tmp = (struct link *)malloc(sizeof(struct link));
		tmp->key = key++;
		tmp->next = h->next;
		tmp->prev = h->next->prev;
		h->next->prev = tmp;
		h->next = tmp;
		return h;
	}
	return 0;
}

void PrintList( struct link *h )
{
	int i = 1;
	double *tmp;

	(struct link *)tmp = h; //snag address of h
	do{
		printf( "%i:%p    key: %i\n    next:%p\n    prev:%p\n", i, h, h->key, h->next, h->prev );
		h = h->next; //go to the next one!
		i++;
	}while( h != (struct link*)tmp );
}

struct link * RemoveElement( struct link *h )
{
	double *tmp;
	(struct link *)tmp = h->prev;

	if( h->next == h->next->next ) //list has one item left, just return it
		return h;

	h->prev->next = h->next;
	h->next->prev = h->prev;

	free( h );

	h = (struct link *)tmp;

	return h;
}

int DeleteList( struct link *h )
{
	double *tmp;

	if( h->next == h->next->next ) // list is empty
	{
		free( h );
		return 1;
	}
	else
	{
		(struct link *)tmp = h->prev;

		h->prev->next = h->next;
		h->next->prev = h->prev;

		free( h );

		h = (struct link *)tmp;
		
		DeleteList( h );
	}
}

void main()
{
	struct link *head;
	int i;
	head = InitList();
	for( i = 0; i < 50; i++ )
		head = AddElement(head);
	PrintList( head );
	for( i = 0; i < 25; i++ )
		head = RemoveElement( head );
	PrintList( head );
	for( i = 0; i < 25; i++ )
		head = AddElement(head);
	PrintList( head );
	DeleteList( head );
}

kobi_hikri · #2 18-Sep-2005, 15:14

Quote:

Originally Posted by Danny

CPP / C++ / C Code:

/***********************************************************
* Problems: Be sure not to print out a list that has already
*           been deleted!  Also, no user input yet.
**********************************************************/

Why not handle this situation ?
Simply print "nothing".
Another point, Why don't you return any value on the

CPP / C++ / C Code:

else

part of your "delete list" function ?

Very nice work,
Kobi Hikri.

Danny · #3 19-Sep-2005, 01:40

Well, first off I should have declared it return void, then replaced

CPP / C++ / C Code:

     return 1;

with

CPP / C++ / C Code:

    return;

That would clear that up.

As for "printing nothing", well, I don't know how to check if a memory address has been free()'ed. I don't even think C keeps track of that sort of thing, so I would have to somehow test for the error (something in Windows like 0xC00000000) which I do not know how to do yet. But then it might not be portable. Anyone know how to do this???

kobi_hikri · #4 19-Sep-2005, 01:52

Quote:

Originally Posted by Danny

Well, first off I should have declared it return void, then replaced

CPP / C++ / C Code:

     return 1;

with

CPP / C++ / C Code:

    return;

That would clear that up.

I try to return excatly the same type I declared as returned value. If you declared

CPP / C++ / C Code:

int

as your returned type, why not return, say '0' or '1' ?
If you choose to implement the deletion as void, why

CPP / C++ / C Code:

return

statement at all ? I would suggest using control flow without

CPP / C++ / C Code:

return

statements inside the body of your function, as it is not a "must" in your function.

Quote:

Originally Posted by Danny

As for "printing nothing", well, I don't know how to check if a memory address has been free()'ed. I don't even think C keeps track of that sort of thing, so I would have to somehow test for the error (something in Windows like 0xC00000000) which I do not know how to do yet. But then it might not be portable. Anyone know how to do this???

Here is a link about your question :
Allocation and deallocation

Notice the allocation log discussed, it's a good idea (not only for c programming).

Best regards,
Kobi Hikri.

WaltP · #5 19-Sep-2005, 02:49

You might also wish to read this info about your declaration of main()

LuciWiz · #6 19-Sep-2005, 06:49

First of, thank you for submitting your code after receiving help on the forum. Not many members do this, but we appreciate more the ones that do.

One more observation:

Quote:

CPP / C++ / C Code:

struct link * AddElement( struct link *h )
{
  static int key = 1;
  struct link *tmp;

  if(h->next == NULL && h->prev == NULL) // List is empty
  {
    h->next = (struct link *)malloc(sizeof(struct link));
    h->next->key = key++;
    h->next->next = h;
    h->prev = h->next;
    h->next->prev = h;
    return h;
  }
  else
  {
    tmp = (struct link *)malloc(sizeof(struct link));
    tmp->key = key++;
    tmp->next = h->next;
    tmp->prev = h->next->prev;
    h->next->prev = tmp;
    h->next = tmp;
    return h;
  }
  return 0;
}

If the condition in the if is met, you get to a return h;. Otherwise, the algo follows the else branch, with the same return statement. So why that last return 0;? It will never come to that anyway.
I would suggest a much cleaner way:

CPP / C++ / C Code:

struct link * AddElement( struct link *h )
{
  static int key = 1;
  struct link *tmp;

  if(h->next == NULL && h->prev == NULL) // List is empty
  {
    h->next = (struct link *)malloc(sizeof(struct link));
    h->next->key = key++;
    h->next->next = h;
    h->prev = h->next;
    h->next->prev = h;
  }
  else
  {
    tmp = (struct link *)malloc(sizeof(struct link));
    tmp->key = key++;
    tmp->next = h->next;
    tmp->prev = h->next->prev;
    h->next->prev = tmp;
    h->next = tmp;
  }
  return h;
}

Plus the proper memory checking. Although unlikely, malloc might fail.

Also, I am not sure if it is my crippled C, but I thought it is a bad practice to cast the result of malloc in C? Just something I read*.

Best regards,
Lucian

* The author said "as opposed to C++". And I say DON'T use malloc at all in C++!

KK2202 · #7 12-Feb-2008, 21:05

Hi all,

I checked the code of the doubly linked list. I want to know how to traverse through a doubly linked list. Say i have an element of the list (the position of which is not known).How would I check if there are any other members in the list ? Currently i check using both prev and next. Is that correct or should i check only using next.

Please provide a good tutorial on Doubly linked list and Circular linked list..All types of linked lists..

Awaiting a positive response.

Thanks in advance,
KK2202

Peter_APIIT · #8 19-Feb-2008, 04:38

Use while loop instead of do loop and do some error checking before proceed to print out ur list or something else.

Use a function to allocate memory rather than when the function popo out, then u node meory also become null.

Please refer to my latest link list program in this forum

I hope this help.

#9 19-Feb-2008, 11:37

Well Danny, your code post is appreciated, though there are numerous "issues" with it (some have already been pointed out).

Code:

dlink.c: In function 'void PrintList(link*)':
dlink.c:72: error: invalid lvalue in assignment
dlink.c:74: warning: format '%p' expects type 'void*', but argument 3 has type 'link*'
dlink.c:74: warning: format '%p' expects type 'void*', but argument 5 has type 'link*'
dlink.c:74: warning: format '%p' expects type 'void*', but argument 6 has type 'link*'
dlink.c: In function 'link* RemoveElement(link*)':
dlink.c:83: error: invalid lvalue in assignment
dlink.c: In function 'int DeleteList(link*)':
dlink.c:109: error: invalid lvalue in assignment
dlink.c: At global scope:
dlink.c:122: error: '::main' must return 'int'

3 errors and 3 warnings.

A "double" as an address? Whew, that's a new one! Why not an unsigned long?

Your "key" logic is fatally flawed. There is no guarantee of uniqueness except when during "creation." What's to prevent a user from modifying the key member of any particular "link" and thereby increasing the likelihood of duplicate "keys?"

Also, what happens to "used keys" during RemoveElement? Shall we assume that they are "banished" from the system forever and thereby are no longer exist?

What purpose or value (to the program) is "key," particularly if a user modifies it. Is a negative key value useful? Otherwise, why is it a signed integer?

There isn't a single occurrence of const in your code. I'd think that somewhere we'd find at least a few of these littered recklessly about...

On the purely architectural side of things:

There is no "list." What you have is an "implied list" based on some "placeholder" into the list that you call "head."

If we consider what the "head" is, isn't it the "most prev" "link" in the list? Likewise, isn't a "tail" the most "next" link in the list? Your code makes your "user" responsible for head and tail differentiation.

Your "AddElement" function is a bit counter-intuitive in terms of what it actually does:

1: it creates a "link"
2: if the "list" is empty, it makes the link the head
3: if the "list" is not empty, it inserts the new "link" after the head and before any remaining links.

If I modify the code in main to just "AddElement" to add 10 elements (links) to the list:

CPP / C++ / C Code:

int main()
{
    struct link *head;
    int i;
    head = InitList();
    for( i = 0; i < 10; i++ )
        head = AddElement(head);
    PrintList( head );

    DeleteList( head );
}

I end up with 11 elements in the list rather than the expected 10, because "InitList" already created a "zero-th" element. How can I ever possibly have a truly empty list? In your code, I really can't. The idea of InitList is to return an empty list that is "ready" for user "links."

Your architectural "model" blends "list management" and "link" management functions into an API that is rather easily confused...particularly since there is "no list" and particularly since there can never be an "empty list" (without a "null head link").

The basic "usefulness" of a doubly linked list is to be able to easily navigate the "links" forward and backward. Other than that, there isn't any significant difference between a doubly linked list and a singularly linked list.

Your code places the responsibility of "link positional detail" on the user of the code, rather than incorporating some of (as much as is possible) responsibility into the "list management infrastructure."

Your choice of "link" for "node" is probably not a terribly unreasonably synonym, however, a "node" is probably a preferred term. The reason why is that a link is a "connection" between one or more nodes. We think of the next and prev pointers as being the "linkage" that connects our "linked list" together. However, an "instance" of a "link" is an individual "element" or "node" in the list.

Your API "blends" the terms, whereas you should strive to use like-terms wherever possible, particularly in "reusable" code.

That is:

AddElement ...does it add an "element" or, as we see from the signature, it takes a structure pointer of type link named, h, which we take to mean "head."

Your "AddElement" should probably take a DLIST* and an ELEMENT* if those are the terms that you're going to use. You see, your AddElement implementation doesn't really just add an element. It creates an element and then adds it. How would I "add" an element to the "list" if I already had an element? Your API does not provide for that functionality.

We also have to ask ourselves, WHY would "(implied List management function named)AddElement" know ANYTHING about what is necessary to Create a new Element?

So, if we had a "ListAddElement" function, we would expect it to simply "add" the element to the list in some predictable fashion. What would be the most predictable fashion?

If we assume that ListAddElement is incorrectly named, we can better understand what List Management functions are required:

CPP / C++ / C Code:

typedef struct st_node
{
    int             value;
    struct st_node* next;
    struct st_node* prev;
} NODE;

typedef struct st_dlist
{
    char  was_dyn_alloc;
    NODE* head;
    NODE* tail;
} DLIST;

// On success: returns a newly allocated, empty NODE
// On failure:   returns a null pointer
NODE*  NodeAllocate();

// On success: returns a newly allocated, empty DLIST
// On failure:   returns a null pointer
DLIST* DListInitialize();

// appends node p_node to tail of dlist p_dlist
// returns pass or fail
int DListAppendNode( DLIST* p_dlist, NODE* p_node );

// inserts node p_node into p_dlist before index, if possible
// returns pass or fail
int DListInsertNodeAt( DLIST* p_dlist, NODE* p_node, const unsigned int index );

...here we have "list management functions" that anyone can easily read and understand that they are going to be working on a specific instance of a "LIST." Their names are rather strong indicators of what we expect them to do with the data that we pass in as arguments.

If we want to create a node, we need a node creation (node management) functions.

Imagine what would happen (and what changes would need to be made) if we wanted to create two lists, one for even numbers and one for odd numbers, for example. Would't we expect to have "list pointers" for "evens" and "odds?"

How would we create a node in each where its value was appropriate for the "expected contents" of the respective lists?

In my abbreviated example above, we would easily expect to:

CPP / C++ / C Code:

int i;

NODE* p_node;

DLIST* p_dlist_even_numbers = DListInitialize();
DLIST* p_dlist_odd_numbers  = DListInitialize();

if( p_dlist_even_numbers != NULL || p_dlist_odd_numbers != NULL )
{
    for( i = 0; i < 100; i++ )
    {
        p_node = NodeAllocate();
        if( p_node != NULL )
        {
            p_node->value = (1 + i);
        }
        else
        {
            return EOM;
        }
        if( p_node->value % 2 == 0 ) // value is even
        {
            ListAppendNode( p_dlist_even_numbers, p_node );
        }
        else // value is odd
        {
            ListAppendNode( p_dlist_odd_numbers, p_node );
        }
    }
}

...

What if we're reading "Node data" from a file? How does "AddElement" do its work as we expect/want?

:davis:

Thread Tools	Search this Thread
Show Printable Version Email this Page	Search this Thread: Advanced Search
Rate This Thread
Rate This Thread:

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Airport Log program using 3D linked List : problem reading from file	batrsau	C Programming Language	11	29-Feb-2008 07:44
[Include] Doubly-linked List	dsmith	C Programming Language	6	14-Apr-2006 13:12
linked list error message	Krandygrl00	C++ Forum	4	22-Jun-2005 14:13
search linked list	itsmecathys	C++ Forum	20	18-Apr-2005 01:34
Insert problem in linked list with two function code	Kay Chan	C++ Forum	1	03-Sep-2004 09:52

Code Snipet For Doubly Linked List

Re: Code Snipet For Doubly Linked List

Re: Code Snipet For Doubly Linked List

Re: Code Snipet For Doubly Linked List