Double linked lists

Code:

---

typdef struct node *link;

struct node {
 
  char item;
  link next;
};

---

So I have to create a list (easy), pass the head to a function called

Code:

---

dlink doublify (link l);

---

(easy)

then I have to convert this list into a double linked list, in essence, instead of only the next pointer (not so easy)

I typedefed a new one,

Code:

---

typedef struct dnode *dlink;

struct dnode {

  char item
  dlink prev, next;
};

---

Now I am not sure how to set for example, the head of the list as the previous to

Code:

---

head->next;

---

And so on and so forth while traversing the list, essentially, making the list a double linked list.

Any tips?

Cheers

1) Do not typedef a struct before it's actually defined.
2) Do not typedef a pointer of some type. Don't typedef, for example, nodeptr as node*, instead use node* as appropriate. It makes the code easier to read.

As for double-linked list... Well, using some logic, it's easy. But I'm not sure what you're trying to achieve. But what I think you need is a pointer to the head or just travel backwards in the list through node->previous until you hit node->previous == NULL, meaning it's the first node in the list.

Quote:

---

Do not typedef a struct before it's actually defined.

---

And why not?

Potential problems at best, I would think.
And it makes no sense to typedef a type that does not exist.

Quote:

---

Originally Posted by Elysia

Potential problems at best, I would think.
And it makes no sense to typedef a type that does not exist.

---

But there are all sorts of reasons to typedef a type that doesn't exist IN THIS SCOPE, particularly for pointers

We can for example have:

Code:

---

// api.h
typedef struct context *pcontext;
...
pcontext createcontext(...);
...

// api.c
...
struct context {
  // stuff goes here
};

...
pcontext createcontext(...)
{
  context *ctxt = new context;
  ...
  return ctxt;
}

---

--
Mats

Again, doing typedefs with pointers instead of type* is just confusing in many situations, especially when mixed inconsistently.
I don't see a reason to typedef pointers instead of just type*.

Quote:

---

Originally Posted by Elysia

Again, doing typedefs with pointers instead of type* is just confusing in many situations, especially when mixed inconsistently.
I don't see a reason to typedef pointers instead of just type*.

---

Ok, so we typedef struct context *context then, and replace "pcontext" with "context *" - the example still holds tho'. It is valid to typedef structs that are not yet in scope.

[In my example I mixed C with C++, and in C++ you don't need typedef for structs and such, as all structs/classes/enums are automatically "typedef struct X X;"]

--
Mats

Quote:

---

Again, doing typedefs with pointers instead of type* is just confusing in many situations, especially when mixed inconsistently.
I don't see a reason to typedef pointers instead of just type*.

---

Typedef of pointer types to iterator types is common in C++. I do not see why it should be unacceptable in C, since we can now talk about links instead of pointers to nodes.

I have seen code implementing typdefs prior to any variables, structs included, being declared. Its placement is purely a coding style. Typedefs, to me are like #defines mainly.

Two good uses of typdefs are for portability and better documentation of the code.


Though some compilers may throw a warning in such placements of typedefs.

Quote:

---

Originally Posted by laserlight

Typedef of pointer types to iterator types is common in C++. I do not see why it should be unacceptable in C, since we can now talk about links instead of pointers to nodes.

---

To long, complex types, typedefs are preferred. However, to simply types where it's just a pointer to the type, I wouldn't recommend it.
I came across some code on the forums some day that was so darn confusing due to the darn typedef, when the code could just have not used the typedef and be much more readable.

The point it, I do not recommend typedefing a pointer in itself, but it's fine to do so on a type. But that may also be a pitfall. One should avoid assigning type X to type Y (even type Y is typedefd to type X).

There may be exceptions to the rule, of course, such as if you're only going to work with type X* (and never X), and assuming you're not going to mess around with the object by passing it where type X* is expected, for example. However, if I see type Y (and not X*), then I also assume I can do y1 = y2.

It's all about readability.

Quote:

---

Originally Posted by slingerland3g

I have seen code implementing typdefs prior to any variables, structs included, being declared. Its placement is purely a coding style. Typedefs, to me are like #defines mainly.

---

I do not agree with that. #define is very unsafe and can cause problems, and is just a search n' replace. Typedef, however, is to be able to use another name for a type. It would tell the compiler "Type X can also be written as Y." Since a compiler can parse a typedef, it shouldn't allow you to do a typedef to something non-existent, such as a type that does not exist. These are my thoughts.

Quote:

---

Though some compilers may throw a warning in such placements of typedefs.

---

This is enough to avoid such placement where portability is desired.

Elysia, sorry to confuse, but I was not stating that typdefs are #defines as they are interpreted by the compiler and not the preprocessor.

Of course, but that doesn't mean you should abuse them ;)

Oh dear, I didn't understand any of that, but I guess it wasn't important for the sake of what I was supposed to do, so I guess I have to just look at the logic that Elysia mentioned in her first post. Thanks, it's just more the logic that I couldn't implement in C syntax for linking the nodes for navigation back and forth.

>> Oh dear, I didn't understand any of that, but I guess it wasn't important for the sake of what I was supposed to do

It wasn't. Don't worry about it J, Elysia is simply documenting her thoughts on typedef, which is merely an alias for a type (FYI). She doesn't like or can't see a use in an incomplete type, which really makes her opinion on the matter rather empty. It's not as if she taught you something.

One example why "forward declaration" could be useful is for hiding implementation, by forward declaring in a header file, and implementing the structure and things in a C file.

Ah nvm, I get what she was kind of talking about.

Not to do:

Code:

---

typedef struct node *link;

---

Instead:

Code:

---

typedef struct node Node;

---

then implement like:

Code:

---

struct node {

 char item
 Node *next, *prev;

};

---

Infact, prior to a couple of days ago, I used to:

Code:

---

typedef struct node Node;

---

format, it was only because I started second session computing in uni and I had a different lecturer, he started using the other format.

Yes. Now that will make your code more readable :)
Which is always a good thing.

Now, as for your question about the linked lists...? What was it again?

How to link the prev pointer to each node so all nodes are linked by an *next and *prev

I can implement *next fine, that's easy, but it doesn't work too well when I try to use the *prev pointer.

The prev pointer works pretty much like the next pointer, but points the other way around, so when you add something to a dlist, you link the prev-pointer of the new node to the previous node, and the next node of the previous node to the new node, for example.

The first nodes prev pointer is NULL [or whatever you use as a end-marker], and the last nodes next pointer is NULL.

--
Mats

Along the lines for a few scenarios of working with double-linked lists, here's a little source snippet from me to demonstrate how a linked list can work:

Code:

---

struct CLinkedListBeginOrEnd
{
        CLinkedList* pBegin;
        CLinkedList* pEnd;
};

CLinkedList* pPrevious;
CLinkedList* pNext;
CLinkedListBeginOrEnd* pBeginOrEnd;

void InsertAfter(CLinkedList* pAdd, CLinkedList* pAfter)
{
        CLinkedList* pNextNode = pAfter->pNext;
        CLinkedList* pPrevNode = pAfter;
        pPrevNode->pNext = pAdd;
        if (pNextNode) pNextNode->pPrevious = pAdd;
        pPrevious = pPrevNode;
        pNext = pNextNode;
        if (pNextNode == NULL) // We're the last node
                pBeginOrEnd->pEnd = this;
}

---

This was actual C++ code converted to C code, but I hope you may still find it relevant to understand how a double linked list works.
Remember: Don't copy. Understand how the code works and you'll get the hang of how a double-linked list works. Then make your own.

Thanks Elysia and matsp, I will review it, the steps are what I need to review, I can code it easily after that. Thanks again !