Doubly Linked List question

[georgewashere]

Hey so I am creating a doubly linked list generic class but I'm having trouble wrapping my head around a piece of code, mainly the code to add an item to the beginning of my list.

my node structure is protected within my class and looks like..

struct Node{
genClass info; // generic type
Node *next, *prev;
Node(genClass el, ElNode *n = 0, ElNode *p = 0)
{ info = el; next = n; prev =p; }
} *head, *tail, *tmp;
genClass el;

The code that I am having trouble understanding is the following :

template<class genClass>
void DoublylinkedList<genClass>::AddToHead(const genClass & el)
{
if(head) {
head = new Node(el,head,0);
head->next->prev = head;
} else 
head=tail=new Node(el);
}

The way I'm currently reading the function is as follows...
1) If the head node contains data(we do not have an empty list)
2) Point the current head node to a new node containing the element passed to AddToHead as the info - but this is where I get confused...

Is the second parameter in the statement head = new Node(el,head,0) assigning the current node as the next node in the list ? How is this possible? Is the head not actually pointing to the new Node until after this statement?

Also the second line of the if block confuses me - I don't understand what's happening.

I think I understand the else statement, it's just saying that we only have one item in the list so the head and tail point to the same node.

[Lowest0ne]

I think one point of confusion is your variable names. Every site I've been to has the same names.

template <class T>
struct Node
{
  T data;
  Node<T> *next, *previous;
  
  Node(const T& data, Node<T>* next = 0, Node<T>* previous = 0) 
    :data(data), next(next), previous(previous)
    {};  
}

template <class T>
class DoublyLinkedList
{
private:
  Node<T> *head;
public:
  DoublyLinkedList() :head(0) {};

  void AddToHead(const T& newData);
};

And here is what you actually ask about :) There are two types of doubly linked lists, circular and not. A circular linked list's head's previous points to the tail, and the tail's next points to the head. This makes it quick to get to the tail to add something at the end of the list.

When your list only has one node, it doesn't really make sense to have it point to itself; those pointers can stay null.

template <class T> 
void DoublyLinkedList::AddToHead(const T& newData)
{
  //  Make a new Node
  Node<T>* newNodePtr = new Node<T>(newData);

  if (!head) // A fresh list :)
  {
    head = newNodePtr;
  }
  else
  {

    if (!head->next)  // The head is the only thing in the list
    {
      head->next = newNodePtr;
      head->previous = newNodePtr;
      newNodePtr->next = head;
      newNodePtr->previous = head;
      
      //Once the connections are made, then make head = newNodePtr;
      head= newNodePtr;
    }
    else  // There is more than one node in the list
    {
      // The ordering of these steps is important, nodes can be lost forever.
      newNodePtr->previous = head->previous // the new node points to the last
      head->previous->next = newNodePtr;  // The last node now points to the new Node

      // Now it is safe to sever the connection between head and tail
      head->previous = newNodePtr;
      newNodePtr->next = head;

      // The Nodes are now linked in a nice circle
      // It doesn't matter what head is, head is just a representation of the beginning of the list.
      head = newNodePtr;
    }
  }
}

Of course, your destructer is important too.

[georgewashere]

Hey thank you for replying to me, you're commented code really helped! I'll return to this topic if I encounter more errors.

[naraku9333]

georgewashere wrote:

Is the second parameter in the statement head = new Node(el,head,0) assigning the current node as the next node in the list ? How is this possible? Is the head not actually pointing to the new Node until after this statement?

The Node ctor sets the second param as the prev pointer in the new Node. Yes after the assignment head points to the new node. The second line sets the old head nodes previous to the new head node.

[Lowest0ne]

When I was mucking around with making a linked list I often had paint open with a drawing of the connections that I was coding.

[georgewashere]

LowestOne that is actually what I'm doing right now - while I understand the general concept behind linked lists I am drawing on paper little structures with boxes representing the variable fields(pointers, info etc.) and pointing them to the appropriate places. Since I'm teaching myself I don;'t have more knowledgeable people by my side to guide me. Whatever gets the job done though (: