Help with linked lists

[Need4Sleep]

Im really trying to get this subject down, but every-time i think im learning i try something on my own and end up bombing the problem. Could someone please show me an example of a basic linked list and explain whats going on? I would appreciate is so much, thanks!

[lwtan90]

Try vector.

[mx760]

a linked list is a collection of individual items called nodes, which has data and at least one pointer to the next node.

A pointer is an address so that it knows where the next node in line is.

What makes linked lists efficient over indexed data structures such as arrays or C++ STL vectors is that it allows for simple insertions and deletions of an item (of a node I mean). The reason is we have a front pointer to keep track of the entire list and a potentail end pointer that points to last node. This way (if for your purposes order of the elements (nodes I mean) don't matter), you can make a new node, point to the front of the list and update front pointer to point to the new node so basically new node becomes new front of the list.

A basic implementation of a linked list node is:

struct node
{
  node* next;//a pointer to next node so you set it to NULL to indicate adding at end of list (so that's where you use the tail pointer)
  int data;//you can have as much data, it could be string, bool whatever
}

Keep in mind that you have to pass by pointers to pointers for your delete node functions as you need to modify the original pointer declared in main. (what I mean is if you use for e.g. void insert_node(node** list, int data); since parameters are passed by value so you need to point to the address of that actual pointer (declared in main) that points to the linked list or you just have a return type to the address of node so I mean: node* insert_node(node* list, int data); and then in main, update the front or end pointers depending of if, for your purposes, you only want to insert new nodes at front or end of list. so you would update these pointers as:
front = insert_node(front, 99); for e.g.

It would be very helpful to read up on pointers and pass by value vs pass by addresses for functions first before diving into linked lists.

[o1vk4iN6]

Think of it as a chain. You can not simply jump to the middle of a link in a chain, you have to start at the beginning or end and continually follow each respective link to the next.

So if you a singly linked list (only one pointer pointing to the next link; no pointer to the previous) and want to add a link you simply make one of the links point to the new link but before that take the old pointer and make the new node point to it. In sense it'd be like cutting a link in a chain, adding a new link and than relinking the rest of the chain.

If you wanted to insert data into the middle of an array you would first need to shift all the other elements over by one.

It's relatively simple:

template< class T >
class list
{
     class node
     {
          node* next;
          T data;
     };

     node *root;
};