Doubly Circular Linked List

[darkknight914]

I need help implementing a Push function for a Doubly Circular Linked List.
This is what I have so far:

//inserts t at the front
template <typename T>
void List<T>::Push(const T& t)
{
 Node * tail = head->next->prev;
 Node * newNode = NewNode(t);
 newNode->next = head->next;
 newNode->prev = tail;
 tail->next = head->next->prev =newNode;
 head->next = newNode;
}

[ne555]

¿so what's the problem?

[nuderobmonkey]

Are you be aware that a circular list has no begin? But it could have an 'end' (if it would be empty).
Because that, I suggest that you Implement your Push method like 'insert' of std::list.

// Inserts a new Node before 'pos'.
//
template <typename T>
Node * List<T>::insert( Node * pos, const T& value)
{
    Node * newNode = NewNode(value);
    newNode->next = pos;
    newNode->prev = pos->prev;
    pos->next->prev = newNode;
    pos->next = newNode;

    return newNode;
}

[Duthomhas]

I presume (from your small piece of code) that you have a structure something like:

template <typename T>
struct Node
{
  Node * next;
  Node * prev;
  T      value;
};

template <typename T>
struct List
{
  Node<T> * head;
  size_t    size;
};

Notice the important property of a node: it has two outgoing pointers: one for the next node in the list and one for the previous. Hopefully you have noticed this is exactly the same for a normal, non-circular linked list.

Now, whenever you are messing with any kind of linked list, you should have a piece of paper and a pencil on hand.

Then you can draw what a list should look like. You should wind up with a piece of paper that looks something like this:

                            List.size = 1
  List.size = 0             List.head
  List.head                     ↓
      ↓                      ╔═════╗
     NULL                 ┌─►║     ╟──┐
                          └──╢     ║◄─┘
                             ╚═════╝        List.size = 3
          List.size = 2                     List.head 
          List.head                             ↓
              ↓                           ┌───────────────────────────────┐    
        ┌─────────────────────┐           │  ╔═════╗   ╔═════╗   ╔═════╗  │
        │  ╔═════╗   ╔═════╗  │           └─►║     ╟──►║     ╟──►║     ╟──┘
        └─►║     ╟──►║     ╟──┘           ┌──╢     ║◄──╢     ║◄──╢     ║◄─┐
        ┌──╢     ║◄──╢     ║◄─┐           │  ╚═════╝   ╚═════╝   ╚═════╝  │
        │  ╚═════╝   ╚═════╝  │           └───────────────────────────────┘
        └─────────────────────┘

Once you have that, the next task is to insert a new node in front of the head, and make it the new head.

This will require drawing new pictures, erasing and moving arrows, etc. If you can do that, then you can make the code do the same thing with the pointers. Keep in mind the special case of 0→1 nodes (push), or 1→0 nodes (pop).

Good luck!

[darkknight914]

I've been trying to draw that, but I'm having trouble correlating the diagram with the nodes and next and prev. I just can't visualize it.

[Duthomhas]

The double-edged box is a node.
The single-lined arrows are pointers.

           ╔═════╗
           ║     ╟──► next
   prev ◄──╢     ║
           ╚═════╝

In a doubly-linked list, the first node’s prev pointer will have the address nullptr, and the last node’s next pointer will also have the address nullptr.

When two nodes are connected, the first’s next pointer will have the address of the second node. Likewise, the second’s prev pointer will have the address of the first node.

             ╔═════╗   ╔═════╗
             ║     ╟──►║     ╟──► nullptr
  nullptr ◄──╢     ║◄──╢     ║
             ╚═════╝   ╚═════╝

In this way, you can traverse all the nodes forward by following the next pointer of each node. Likewise, you can find all nodes going backward by following the prev pointers.


In a circular list, the difference is that there are no nullptr pointers; the list wraps around. The beginning (or head) of the list is considered the first node in the list, even though it is a circle.

Here is a list of eight nodes containing the numbers 1, 2, 3, …, 8:

            List.size = 8
            List.head
                ↓
   ╔═════╗   ╔═════╗   ╔═════╗
   ║  8  ╟──►║  1  ╟──►║  2  ║
   ║     ║◄──╢     ║◄──╢     ║
   ╚═══╤═╝   ╚═════╝   ╚═══╤═╝
     ▲ ▼                 ▲ ▼
   ╔═╧═══╗             ╔═╧═══╗
   ║  7  ║             ║  3  ║
   ║     ║             ║     ║
   ╚═══╤═╝             ╚═══╤═╝
     ▲ ▼                 ▲ ▼
   ╔═╧═══╗   ╔═════╗   ╔═╧═══╗
   ║  6  ╟──►║  5  ╟──►║  4  ║
   ║     ║◄──╢     ║◄──╢     ║
   ╚═════╝   ╚═════╝   ╚═════╝

Notice that, if you push a new node in “front” of the head node, it will go between 1 and 8, and the head pointer will be updated to reflect the change. Here, we “push” a new node with the value = 100:

            List.size = 9
            List.head      (used to be the head)
                ↓           ↓
   ╔═════╗   ╔═════╗   ╔═════╗   ╔═════╗
   ║  8  ╟──►║ 100 ╟──►║  1  ╟──►║  2  ║
   ║     ║◄──╢     ║◄──╢     ║◄──╢     ║
   ╚═══╤═╝   ╚═════╝   ╚═════╝   ╚═══╤═╝
     ▲ ▼        ↑                  ▲ ▼
   ╔═╧═══╗    (new node)         ╔═╧═══╗
   ║  7  ║                       ║  3  ║
   ║     ║                       ║     ║
   ╚═══╤═╝                       ╚═══╤═╝
     ▲ ▼                           ▲ ▼
   ╔═╧═══╗        ╔═════╗        ╔═╧═══╗
   ║  6  ╟───────►║  5  ╟───────►║  4  ║
   ║     ║◄───────╢     ║◄───────╢     ║
   ╚═════╝        ╚═════╝        ╚═════╝

The new node with value 100 was inserted between the head node and the last node in the circle. Then the head was changed to point to the new head.


Get used to seeing diagrams like this, especially when talking about pointers and linked lists and the like.

Hope this helps.

[keskiverto]

If "Push" adds to the "front", then one could have slightly simpler "PushBack" too and implement the former with the latter:

void List<T>::Push(const T& t)
{
  PushBack( t );
  head = head->prev;
}

[Duthomhas]

@keskiverto
That breaks it.