Thread: sorted linked list

  1. #1

    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
    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.
    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....
    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
    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....
    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 
    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 
    adding the 1 is just a compare then add at front to get
    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 :-

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, 06:39 PM
  3. Linked List
    By jpipitone in forum C Programming
    Replies: 4
    Last Post: 03-30-2003, 09:27 PM
  4. problem with structures and linked list
    By Gkitty in forum C Programming
    Replies: 6
    Last Post: 12-12-2002, 06:40 PM
  5. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 10:21 PM