Thread: Circular linked list

  1. #1
    Registered User
    Join Date
    Jun 2004
    Posts
    40

    Circular linked list

    If I have an external pointer List pointing to the "last" node, would this statemnet disconnect the node at the "beginning" of the list??
    Thanks!!

    Code:
    Cur = List -> Next;
    List -> Next = Cur -> Next;

  2. #2
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,897
    Have you tried it? Did it work?
    My best code is written with the delete key.

  3. #3
    Registered User
    Join Date
    Jun 2004
    Posts
    40
    No, I did not write a program, I am just reading and learning about linked lists and I am trying to make sure I am understanding what I am reading.

  4. #4
    Disturbed Boy gustavosserra's Avatar
    Join Date
    Apr 2003
    Posts
    244
    I think yes! Cur would be pointing to first. Then the next of the last (the first) will be pointing to next of the first, so, no one will be pointing to first. But usually the linked list is a pointer to the first element.
    Nothing more to tell about me...
    Happy day =)

  5. #5
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,897
    >I am trying to make sure I am understanding what I am reading.
    The best way to check your understanding is to write a small program that tests your assumptions:
    Code:
    /* Ugly quick code */
    #include <iostream>
    
    using namespace std;
    
    struct node {
      int   data;
      node *next;
      node(int init, node *link)
        : data(init)
        , next(link)
      {}
    };
    
    int
    main()
    {
      node *head, *tail;
    
      head = new node(0, 0);
      head->next = head;
      tail = head;
      for (int i = 1; i < 10; i++) {
        tail->next = new node(i, head);
        tail = tail->next;
      }
      for (tail = head; tail->next != head; tail = tail->next) {
        cout<< tail->data <<endl;
      }
      cout<< tail->data <<endl<<endl;
      node *cur = tail->next;
      tail->next = cur->next;
      for (tail = head; tail->next != head; tail = tail->next) {
        cout<< tail->data <<endl;
      }
      cout<< tail->data <<endl;
    }
    This clearly doesn't work when you run it. The problem is that tail->next will never point to head because head is the node that was removed from the list. You need to reseat head too:
    Code:
    node *cur = tail->next;
    tail->next = cur->next;
    head = tail->next;
    My best code is written with the delete key.

  6. #6
    Disturbed Boy gustavosserra's Avatar
    Join Date
    Apr 2003
    Posts
    244
    Hi Prelude! Just a question about your code. I know that is that only way to initialize const member, but way use that kind of initialization in node constructor instead of inside the definition?
    Sorry for changing the topic a little bit.
    Nothing more to tell about me...
    Happy day =)

  7. #7
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,897
    >but way use that kind of initialization in node constructor instead of inside the definition?
    Because it never hurts and sometimes helps (in the case of const or reference members or avoiding default construction and then assignment for objects). I try to use an initialization list for my constructors as much as possible to remain consistent and avoid hairy situations.
    My best code is written with the delete key.

  8. #8
    Disturbed Boy gustavosserra's Avatar
    Join Date
    Apr 2003
    Posts
    244
    Ok! Thanks!
    Nothing more to tell about me...
    Happy day =)

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Duplicating value of pointer to linked list
    By zephyrcat in forum C Programming
    Replies: 14
    Last Post: 01-22-2008, 03:19 PM
  2. circular doubly linked list help
    By gunnerz in forum C++ Programming
    Replies: 5
    Last Post: 04-28-2007, 08:38 PM
  3. singly linked to doubly linked
    By jsbeckton in forum C Programming
    Replies: 10
    Last Post: 11-06-2005, 07:47 PM
  4. Problem with linked list ADT and incomplete structure
    By prawntoast in forum C Programming
    Replies: 1
    Last Post: 04-30-2005, 01:29 AM
  5. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 10:21 PM