insertion in a sorted linked list

This is a discussion on insertion in a sorted linked list within the C Programming forums, part of the General Programming Boards category; Is there a special way of inserting in a sorted linked list?(<O(n))...

  1. #1
    Registered User
    Join Date
    Mar 2008
    Posts
    2

    insertion in a sorted linked list

    Is there a special way of inserting in a sorted linked list?(<O(n))

  2. #2
    Registered User
    Join Date
    Nov 2004
    Location
    India
    Posts
    515
    If you are talking about a singly linked list then the answer is no.
    Code:
    >+++++++++[<++++++++>-]<.>+++++++[<++++>-]<+.+++++++..+++.[-]>++++++++[<++++>-] <.>+++++++++++[<++++++++>-]<-.--------.+++.------.--------.[-]>++++++++[<++++>- ]<+.[-]++++++++++.

  3. #3
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,269
    Quote Originally Posted by sagsriv View Post
    Is there a special way of inserting in a sorted linked list?(<O(n))
    In general, no there isn't. However you can get amortised O(log n) insertion time into a skiplist.
    However, if you have a lot of insertions to do, you can store a small sorted selection of those nodes in a temporary array and allow an O(log n) search time.

    There are many alternatives to what you're doing, as well:
    If you have a bunch of items to insert then you could first sort the items to be inserted, then do a merge pass on the two lists.
    Perhaps you can simply add them to the end, and re-sort the list every now and then.
    Another idea is using a self-balancing binary tree instead.

    It would be best for you to give more background on what the list insertions are part of. Show us the bigger picture.
    Last edited by iMalc; 03-15-2008 at 01:33 PM.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  4. #4
    Registered User
    Join Date
    Mar 2008
    Posts
    2
    Thanx PING and iMalc. Actually, I have seen this question (insert an element in a sorted linked list) in lots of technical interview papers. So, I thought there was something special with this 'sorted' term,as, in an array, we would have used a binary search first, then place the number in the proper position. But for linked list, this option is not time efficient (is it?).Nyways, seems these interviewers try to baffle people with dis typo questions.

  5. #5
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    Quote Originally Posted by sagsriv View Post
    But for linked list, this option is not time efficient (is it?).
    Well, if coded correctly, O(impossible) can finish pretty quickly. But no, you don't have random access to the elements of a linked list, so you can't do binary search.

    I realize that I'm a mere academic, but I would guess the point of this interview question would not be to worry about speed, but just to get it right (off the top of my head, given a standard sorted linked list, I can think of exactly one way to do it).

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Linked List Not Saving Value as Int
    By bar338 in forum C Programming
    Replies: 4
    Last Post: 05-04-2009, 07:53 PM
  2. Unknown memory leak with linked lists...
    By RaDeuX in forum C Programming
    Replies: 6
    Last Post: 12-07-2008, 03:09 AM
  3. circular doubly linked list help
    By gunnerz in forum C++ Programming
    Replies: 5
    Last Post: 04-28-2007, 08:38 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

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