sorted linked list

This is a discussion on sorted linked list within the C++ Programming forums, part of the General Programming Boards category; if i have a linked list struct node { int item; node* next; }; can someone please show me an ...

  1. #1
    Unregistered
    Guest

    sorted linked list

    if i have a linked list
    struct node
    {
    int item;
    node* next;
    };
    can someone please show me an example of how i would sort this list.
    thanks in advance

  2. #2
    Skunkmeister Stoned_Coder's Avatar
    Join Date
    Aug 2001
    Posts
    2,572
    It is usual to keep a linked list sorted. That means rather than just inserting new nodes at the head or tail of the list you insert them at the right place.
    Lets build a list with your example we will add the numbers 3,4,2,6,5,1 like this.
    Code:
    head of list is a null pointer of type node*
    allocate memory for a node using new assigning pointer to head
    add 3 to data field
    add null to next field (i.e. no next node)
    list looks like....
    3--NULL
    now we need to add a new node to hold the value 4.
    compare 4 to head->item
    if less add at front. but its not so we compare to next node and there isn't one so call insert at back func.
    list now looks like
    3--4--NULL
    now we compare 2 to head->item and find its less so call add at front func to end up with a new list like....
    2--3--4--NULL
    now we compare 6 to head->item and find its greater so we traverse the list until we find where to insert. 
    In this case its a call to insert at back func again
    list now looks like 
    2--3--4--6--NULL
    now we add 5 so we compare again to head->item and follow the next pointers through the list until we compare to 6 and find its less so we insert new node just before 6
    list now looks like 
    2--3--4--5--6--NULL
    adding the 1 is just a compare then add at front to get
    1--2--3--4--5--6--NULL
    and your list is sorted as its built.
    The inserts are nothing more than a bit of pointer manipulation and dynamic memory allocation.
    Free the weed!! Class B to class C is not good enough!!
    And the FAQ is here :- http://faq.cprogramming.com/cgi-bin/smartfaq.cgi

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. C++ Linked list program need help !!!
    By dcoll025 in forum C++ Programming
    Replies: 1
    Last Post: 04-20-2009, 10:03 AM
  2. Replies: 5
    Last Post: 11-04-2006, 05:39 PM
  3. Linked List
    By jpipitone in forum C Programming
    Replies: 4
    Last Post: 03-30-2003, 08:27 PM
  4. problem with structures and linked list
    By Gkitty in forum C Programming
    Replies: 6
    Last Post: 12-12-2002, 05:40 PM
  5. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 10:21 PM

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