insertion in an ordered list ?

This is a discussion on insertion in an ordered list ? within the C Programming forums, part of the General Programming Boards category; hello..... assume i have an ordered list (sorted).... is it possible to insert an element in the list in O(lgn) ...

  1. #1
    Registered User
    Join Date
    Jan 2009
    Posts
    71

    insertion in an ordered list ?

    hello.....

    assume i have an ordered list (sorted).... is it possible to insert an element in the list in O(lgn) time ?....

    i dont think a list can be maintained as an array...since shifting all the elements during insertion will again result in O(n)........

    if a linkedlist is used...how do i search for the elements ? because in linked lists..we lose the power to access any element in O(1) time...

    if it is possible to insert an element in an linked list in logarithmic time ??

    plz help !

    thank u very much !

  2. #2
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,659
    Quote Originally Posted by jack_carver
    assume i have an ordered list (sorted).... is it possible to insert an element in the list in O(lgn) time ?....
    It is possible if you use say, a balanced binary tree to store your list.

    Quote Originally Posted by jack_carver
    i dont think a list can be maintained as an array...since shifting all the elements during insertion will again result in O(n)........
    Yes, unless you are always going to insert at the end (i.e., your input sequence is already sorted).

    Quote Originally Posted by jack_carver
    if it is possible to insert an element in an linked list in logarithmic time ??
    Since you are talking about a sorted linked list in general, I believe the answer is no.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. help with nodeType function?
    By chullen in forum C++ Programming
    Replies: 25
    Last Post: 11-05-2006, 02:32 AM
  2. Problem with linked list ADT and incomplete structure
    By prawntoast in forum C Programming
    Replies: 1
    Last Post: 04-30-2005, 01:29 AM
  3. Linked List Help
    By CJ7Mudrover in forum C Programming
    Replies: 9
    Last Post: 03-10-2004, 09:33 PM
  4. Linked list with two class types within template.
    By SilasP in forum C++ Programming
    Replies: 3
    Last Post: 02-09-2002, 05:13 AM
  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