Because a linked list stores a list of items, it has some similarities to an array. But the two are implemented quite differently. An array is a single piece of memory while a linked list contains as many pieces of memory as there are items in the list. Obviously, if your links get messed up, you not only lose part of the list, but you will lose any reference to those items no longer included in the list (unless you store another pointer to those items somewhere).

Some advantages that a linked list has over an array are that you can quickly insert and delete items in a linked list. Inserting and deleting items in an array requires you to either make room for new items or fill the "hole" left by deleting an item. With a linked list, you simply rearrange those pointers that are affected by the change. Linked lists also allow you to have different-sized nodes in the list. Some disadvantages to linked lists include that they are quite difficult to sort. Also, you cannot immediately locate, say, the hundredth element in a linked list the way you can in an array. Instead, you must traverse the list until you've found the hundredth element.

A linked list like I've described above, where each item has a pointer to the next item in the list, is called a singly linked list. To implement this list, you would also want to store a pointer to the first item in the list (the head), which you would use to access the other items. However, some operations are awkward with a singly linked list. For example, to remove an item, you may need to traverse the entire list to locate the item that came before the item you are removing in order to modify its NEXT pointer. For this reason, many linked lists are implemented as a doubly linked list. In a doubly linked list, each item contains a pointer to both the next and the previous item in the list. Because you may want to traverse the list in reverse order, you would probably want to store the last item in the list (the tail) in addition to the first item.

The code below shows some key routines to implement a doubly linked list. The NODE structure represents each node in the list. It includes an int for storing information and a pointer to the next and previous nodes in the list. Obviously, you can modify the NODE structure to store other types of data and this code is ideally suited for conversion to a template that can be compiled to work with any other type of data. In addition, all the list-related routines are ideally suited to be implemented as a class. I kept the code as straight C here just to keep things as simple as possible and to fit the code into the space I had available. Perhaps you can modify it to meet your own needs.

#include 

struct NODE {
   NODE *pNext;
   NODE *pPrev;
   int nData;
};

NODE *pHead, *pTail;

// Appends a node to the end of the list
void AppendNode(NODE *pNode)
{
   if (pHead == NULL) {
      pHead = pNode;
      pNode->pPrev = NULL;
   }
   else {
      pTail->pNext = pNode;
      pNode->pPrev = pTail;
   }
   pTail = pNode;
   pNode->pNext = NULL;
}

// Inserts a node into the list after pAfter
void InsertNode(NODE *pNode, NODE *pAfter)
{
   pNode->pNext = pAfter->pNext;
   pNode->pPrev = pAfter;
   if (pAfter->pNext != NULL)
      pAfter->pNext->pPrev = pNode;
   else
      pTail = pNode;
   pAfter->pNext = pNode;
}

// Removes the specified node from the list
void RemoveNode(NODE *pNode)
{
   if (pNode->pPrev == NULL)
      pHead = pNode->pNext;
   else
      pNode->pPrev->pNext = pNode->pNext;
   if (pNode->pNext == NULL)
      pTail = pNode->pPrev;
   else
      pNode->pNext->pPrev = pNode->pPrev;
}

// Deletes the entire list
void DeleteAllNodes()
{
   while (pHead != NULL)
      RemoveNode(pHead);
}

void main()
{
   NODE *pNode;

   // Add items to linked list
   for (int i = 0; i < 100; i++) {
      pNode = new NODE;
      pNode->nData = i;
      AppendNode(pNode);
   }
   // Now display each item in list
   for (pNode = pHead; pNode != NULL; pNode = pNode->pNext) {
      printf("%d\n", pNode->nData);
   }
   //
   DeleteAllNodes();
}