Thread: insertion in an ordered list ?

  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
    28,413
    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.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    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, 03: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, 10:33 PM
  4. Linked list with two class types within template.
    By SilasP in forum C++ Programming
    Replies: 3
    Last Post: 02-09-2002, 06:13 AM
  5. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 10:21 PM