Doubly Linked List 1

[RVDK]

Hi I'm trying to write code for a doubly linked list. I have some trouble understanding linked list arrays and structures. This is what I have, would anyone please be able to help me figure out what I'm doing wrong? Thank you.

/*
* linkstack.c
*
* A stack implemented as a linked list
*/
#include <stdio.h>
#include <stdlib.h>

typedef struct Node
{
int element;
struct Node *next;
struct Node *prev;
} Node;

Node *head = 0;

void print_stack ( )
{
Node *p = head;
printf ("Top:");
while ( p )
{
printf ("[%d]", p->element );
p = p->next;
}
printf (":Bottom\n");
}

void addsorted (int value)
{

Node *n = (Node *)malloc(sizeof(Node));
n->next=NULL;
n->element = value;
if(!head)
{
head = n;
}
else
{
Node *p = head;
if (n->element > head)
{
while(p->next != NULL)
{
if (n->element > p->next)
{
p = p->next;
}
else
{
p->next->prev = n;
n->prev = p->prev;
p->prev = n;
n->next = p;
}
}
p->next = n;

}
}

int main ()
{
addsorted(9);
addsorted(15);
addsorted(4);
print_stack();



return 0;
}

 

[ArkM]

1. Use CODE tag to present your snippets (see Process TGML link on the form).
2. Be careful: you compare int elements with node pointers in a search loop. Can you read your compiler diagnostics about these wrong comparations?.
3. Optional: don't use old NULL macros, write a simple 0...

Correct then retry (to debug you alg...

 

[TaintedFlames]

Hey,
First thing, you might want an list struct, to hold you head and tail. Second you don't want your node to be public, that's a habbit to start.

Also, you don't want to do this:

Node *head = 0;
\\Instead this
Node *head = NULL;
[\code]
It's more or less the same thing, but you shouldn't think of a pointer as 0.

You should really look at linked list more. You normally have 2 structs, not declared public, but in your main. Your code is quite sloppy, but no worries. Read more about linked list and if you get stuck again post it.


 

Jay

 

[RVDK]

Hi, actually my biggest problem is finding somewhere where I can actually read more about linked lists. I have trouble understanding how they're implemented and I need a breakdown of the code to understand, a tutorial or something if possible. I've been working on this a bit more but it's still quite wrong. I can add elements without worrying about order:

void add_front (int value)
{
Node *n = (Node *)malloc(sizeof(Node));
n->element = value;
n->next = head;
head = n;
}

But anything more complex is beyond me, so far.

 

[TaintedFlames]

Hey RVDK,
I can run a quick description by you see if it helps.
1)It's a lot easier if you have a Node struct and List Struct. In your node strcut, you have your int, with 2 node pointer(next and previous). In your List struct, you should have 2 node pointers(Head and Tail).

2) Another thing to keep in mind, is that you probably want to order your linked list. Because if you don't, it because a stack. But you might not want to worry about it now.

3) Now your addfront() function is basicly a Push() function for a stack. What you want to do here is:
a)Create a new node
b)Make the current head's next = your new node
c)Make your new node's previous = head
d)Make head your new node.
Make sure that you follow this in order
Now keep in mind that you're going to have to clean up your memory somehow. You might want to use a recursive delete function that runs threw your List.

4) Your print_all function should be quite easy.

Node * Current;
Current = list->Head;
while(!Current){
printf("%n\n",Current->element);
Current= Current->Next;
}

I hope this gives you an idea on how linked lists work!



Jay

 

[DaveSinkula]

Hi, actually my biggest problem is finding somewhere where I can actually read more about linked lists. I have trouble understanding how they're implemented and I need a breakdown of the code to understand, a tutorial or something if possible.

Perhaps this?

 

[jstreich]

In general... when working on a data structure... draw it. Every funtion you add. Draw each step in inserting, deleteing and iterating. This way you can SEE what is going on before you write it. A doubly linked list can be complicated, but it's not as big of a headache as a avl tree, red/black tree, b*tree or other structure. If you draw them first, then looking at the code you can follow the drawing to SEE where the special cases are.

In general, empty list, last and/or first element of a linked list are special cases and everything else is a sunnyday case. But with larger and more complicated structures drawing it is the best way to see where the problem arise.

[plug=shameless]

http://game-master.us/phpx-3.4.0/

[/plug]

 

[RVDK]

Thanks for your help, I think I've figured it out. Have a great weekend.