Linked List question

This is a discussion on Linked List question within the C++ Programming forums, part of the General Programming Boards category; When inserting data value into unsorted linked list, where is most efficient to add the new data value? Before first ...

  1. #1
    Registered User
    Join Date
    Mar 2011
    Posts
    14

    Linked List question

    When inserting data value into unsorted linked list, where is most efficient to add the new data value? Before first element? After last element?

    When Inserting into unsorted array-based list, where is most efficient position to add new data value?

    Also, most efficient way to delete data value from sorted array-based list?
    -locate position and shift each value one position towards beginning of array, towards end of array?

  2. #2
    Programming King Mr.777's Avatar
    Join Date
    Mar 2011
    Location
    Middle of NoWhere
    Posts
    320
    Add to front and delete from last.
    I don't care if someone doesn't like me, i was not put on earth to entertain everyone.

    No King, no Queen, I am the ACE of battle.

  3. #3
    Registered User
    Join Date
    Mar 2011
    Posts
    14
    Quote Originally Posted by Mr.777 View Post
    Add to front and delete from last.
    add to front for both linked list and array-based?

    And when you say delete from last, do you mean locate array position, shift value one position towards the end of array? Or locate position, then overwrite value to be deleted with last value stored in container?

  4. #4
    C++ Junkie Mozza314's Avatar
    Join Date
    Jan 2011
    Location
    Australia
    Posts
    174
    Quote Originally Posted by ee1215 View Post
    When inserting data value into unsorted linked list, where is most efficient to add the new data value? Before first element? After last element?

    When Inserting into unsorted array-based list, where is most efficient position to add new data value?

    Also, most efficient way to delete data value from sorted array-based list?
    -locate position and shift each value one position towards beginning of array, towards end of array?
    I don't know why you specify an unsorted linked list. A linked list is not inherently sorted, its data may just happen to be sorted, just like an array. It is equally efficient to add an element to the start of the linked list as it is to add it to the end of the linked list. If you already have an iterator to another position, it's also just as efficient to add an element before the element represented by that iterator. This is assuming you're working with the STL std::list, otherwise it depends on the specific implementation of a linked list you're using, as always. The following applies to linked lists in general though - there is no need to delete a different element or shuffle other elements to make room for it.

    Can you clarify what you mean by "sorted array-based list"? As far as I'm concerned, if you have "array-based" data, the term "list" can only apply in the everyday sense of the word, it's not a linked list.

    If you really just have a sorted array of data and want to add a new element, there's really only one appropriate way to do it. First check that there's room in the array left for you to add an element. Then use a binary search to find the first element less than or equal than the element you want to insert. Then shift all of the elements after that forward by one and insert your element after that element you found with the binary search.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. linked list question
    By brb9412 in forum C Programming
    Replies: 16
    Last Post: 01-04-2009, 03:05 PM
  2. Sorting linked list please help with CODE
    By scarlet00014 in forum C Programming
    Replies: 3
    Last Post: 09-27-2008, 11:24 PM
  3. Reverse function for linked list
    By Brigs76 in forum C++ Programming
    Replies: 1
    Last Post: 10-25-2006, 10:01 AM
  4. Anyone good with linked list.....I am not....
    By chadsxe in forum C++ Programming
    Replies: 11
    Last Post: 11-10-2005, 01:48 PM
  5. Linked list with two class types within template.
    By SilasP in forum C++ Programming
    Replies: 3
    Last Post: 02-09-2002, 05:13 AM

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