Thread: Delete an item from a linked list

  1. #1
    Banned
    Join Date
    Apr 2015
    Posts
    596

    Delete an item from a linked list

    Hi gentlemen, there's something really confusing me which is:
    how would I delete an item from a linked list when all
    I get is the item itself. ?

    any reasonable approach to share with me? thanks alot.

    I've wrote a code but the time complexity is O(n) (searching for the element and if found => delete it ) , I need to decrease the time complexity of deletion ..


  2. #2
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    37,484
    Show us your code.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  3. #3
    Registered User
    Join Date
    Dec 2017
    Posts
    630
    unbelievable
    The world hangs on a thin thread, and that is the psyche of man. - Carl Jung

  4. #4
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    27,148
    Quote Originally Posted by RyanC
    I need to decrease the time complexity of deletion
    Use a doubly linked list instead, upon which deletion given a pointer to the node becomes a constant time operation. If you insist on a singly linked list, then change it such that you receive a pointer to the previous node instead, with some special case for the head. If you insist on having both a singly linked list and receiving a pointer to the node to be deleted, then you either accept a linear time average and worst case, or you commit seppuku. Good luck!
    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. Replies: 4
    Last Post: 04-25-2008, 02:37 AM
  2. how to add new item at the end of linked list
    By raghu_equinox in forum C Programming
    Replies: 3
    Last Post: 10-11-2006, 01:00 PM
  3. how to remove last item of linked list please
    By raghu_equinox in forum C Programming
    Replies: 6
    Last Post: 10-11-2006, 03:04 AM
  4. add linked list item to the top
    By xion in forum C++ Programming
    Replies: 8
    Last Post: 02-12-2005, 08:59 AM
  5. delete item from linked list
    By lambs4 in forum C Programming
    Replies: 2
    Last Post: 03-28-2003, 11:06 AM

Tags for this Thread