Linked List

darkknight914 (37)
How do you add a new_Node directly behind the last_Node in a circular linked list when it is full?

Would it be like this:


1
2
3
4
 
Queuenode * new_Node = new Link (q);
last_Node->nextNode = new_Node;
last_Node = new_Node;

Last edited on
keskiverto (10402)
A circular list is by definition "always full", except when it is empty.

You have in list
A -- B

where A.next == B

You want to have
A -- C -- B

Obviously A.next == C, but also C.next == B
Your code does not ensure that. Yet.


It is up to the behaviour of your list, whether the last_Node updates on insert.
jonnin (11438)
I believe the original poster's code is missing a
last_Node->nextNode = firstNode;
which is probably easier to do with this:

1
2
3
4
5
 
Queuenode * new_Node = new Link (q);
Queuenode * tmp = last_Node->nextNode; //head, firstnode...  if you have this already, don't need tmp. 
last_Node->nextNode = new_Node;
last_Node = new_Node;
last_Node->nextNode = tmp;  //or if have it already, use that variable...


good learning experience but I would have built this off a vector, then you can push-back into this location for 'free' and a simple iteration %size() makes it circular. Unless you also insert into the middle of the thing, but it says queue in the name, so I was guessing not (?).
Last edited on
darkknight914 (37)
1.When the ring is null, that is when firstNode == nullptr, a Push operation must create two links, one at each of firstNode and last_Node. The data item is held in firstNode, what is held in last_Node is immaterial. Some people use the same value, other people use the default T object T(). Be sure also that these two link objects point to each other with their nextNode pointers. Thus you now have a carrier ring with the requisite extra node pointed to by last_Node.

2. When the carrier ring is full, indicated by last_Node->nextNode == firstNode, a new node must be created and linked into the ring. We do this by linking the new node in directly behind last_Node.

3. When the carrier ring is not full (neither case 1 or 2) we already have a spare link object behind last_Node.

In either case 2 or 3 we can now assign q into last_Node-> data and then advance last_Node.

This is what I have for the Push function, but I'm struggling with it.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
 
void Push(const& q)
{
    if (firstNode == nullptr))
    { 
      firsNode = newLink(q);    // where newLink is Queuenode * newLink = newLink(q)
      last_Node = newLink(q);
      firstNode-> nextNode = last_Node;
      firstNode = last_Node;

    }
    if (last_Node -> nextNode == firstNode)
    {
      Queuenode* new_Node = newLink(q);
      last_Node -> nextNode = new_Node;
      last_Node = new_Node;
      last_Node -> next_ = firstNode;
    
      // can now assign q into last_Node-> data and then advance last_Node.
      last_Node -> data = q;
      last_Node = firstNode -> nextNode;
    }

    else 
    { 
       last_Node -> data = q;
       last_Node = firstNode -> nextNode;
    }


Last edited on
dhayden (5798)
What do you mean by "when the ring is full?" Do you just mean that it isn't empty?
Push may be easier than you think:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
 
void
Push(const &q)
{
    Queuenode newNode = newLink(q);
    if (firstNode) {
        // If firstNode then last_Node exists too. Add it behind last_Node
        last_Node->nextNode = newNode;
    } else {
        // Insert into empty list.
        firstNode = newNode;
    }
    // Either way, newNode points back to firstNode, which is guaranteed
    // to be set by now.
    newNode->nextNode = firstNode;
    // And either way, last_Node advances to newNode
    last_Node = newNode;
}

darkknight914 (37)
At any given time, the carrier ring must have at least one link more than the size of the queue in order to distinguish between the "empty queue" and "full carrier" states. The "queue support" consists of the links from firstNode to (but not including) last_Node.

I tried dhayden's approach, but now its infinitely looping when I try to display it.
Last edited on
keskiverto (10402)
How do you display it then? A cycle repeats infinitely by definition.
darkknight914 (37)
I'm using a display function.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
 

void Display(std::ostream& os) const
{

if (Empty())
      return;
    Queuenode* curr_link = firstNode;
    if (ofc_ != '\0')         // char ofc is a private variable in my class
    {
      while (curr_link != nullptr)
      {
        os << ofc_ << curr_link-> data_;          // data is a private variable in my class
        curr_link = curr_link -> nextNode;
      }
    }
    else
    {
      while (curr_link != nullptr)
      {
        os << curr_link -> data_;
        curr_link = curr_link -> nextNode;
      } 
    } 
  }

jonnin (11438)
pick any node to start at.
loop until you get back to that node, displaying as you go.

darkknight914 (37)
How do you mean?
doug4 (1538)
If you loop until curr_link is nullptr, then you either:
- will loop forever
or
- you don't have a circular linked list.

If your linked list is circular, then the "last" node's nextNode pointer will point to the first node, and your loop will continue forever.

So, is your linked list circular?
darkknight914 (37)
Yes my linked list is circular. So you're saying to use my last_Node instead of the nullptr?
doug4 (1538)
Try it and see what you get. Make sure the entire list is printed....
darkknight914 (37)
Before it was infinitely looping. I used dhayden's approach above, but after I changed the nullptr to firstNode it didn't display anything.
dhayden (5798)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
void Display(std::ostream& os) const
{

if (Empty())
return;

Queuenode* curr_link = firstNode;
char *buf[2] {}; // zero-initialize
if (ofc_) buf[0] = ofc_;
do {
os << buf << curr_link-> data_;    // Print first
curr_link = curr_link -> nextNode; // and then increment
while (curr_link != fisrtNode);
}
Topic archived. No new replies allowed.