Linked List Queue

[BretFlorida]

can someone please help me, i still cant understand linked list, ive done a code but i need it to be implemented as a linked list, can someone please help me.

[TheBigH]

Basically, each link in a linked list is a structure containing two things: the data you're storing, and a pointer to the next link in the list.

What have you tried? Show us your code.

[rcgldr]

For a more general version of a linked list, you want the link to the next element to the first element in the class or structure. If this is to be a double linked list, then the pointers to previous and next should be the first two elements (the order of previous or next doesn't matter). In the case of C++ and a class, you can create a link node class that just contains a pointer to the next node, then use this for an inherited class that also has data elements.

[Malcolm McLean]

Here's the guts of a linked list.

typedef struct node
{
  struct node *next;
  struct node *prev;
  void *data; /* could be anything, just a pointer to hang the payload off */
} NODE;

You set it up so that you can have arbitrarily many nodes, with the next pointer pointing to the next one in the chain, and the prev pointer pointing to the previous one. Imagine it as a line of children holding hands.

You need a special pointer somewhere to point to the first element, and often, for efficiency, to the last. Then you can find any element by going down the next pointers. You can add or subtract elements from any position, though for a queue you need only consider the case where you are adding to the tail and subtracting from the head.

Its normal to call malloc() to create each node. Then you can have as many nodes as the computer's memory will allow.

[rcgldr]

Since you mentioned queue, you probably only need to retrieve elements from the front of the queue and append them to the end of the queue. This is called a fifo (first in first out). The structures would look like:

typedef struct _NODE{
struct _NODE *next;
DATA data; /* this could be just about anything */
}NODE, *PNODE;

typedef struct{
NODE *first;
NODE *last;
}QUEUE, *PQUEUE;

QUEUE queue;

Initally queue.first and queue.last pointers are set to NULL. If there's only one node, then both queue.first and queue.last point to the same node. If there are multiple nodes, then queue.first points to the first node, the first node's next pointer points to the second node and so on. The last node's next pointer is set to NULL.