Deleting a middle node from a single linked list when pointer to the previous node is not available

by

It’s definitely more a quiz rather than a real problem. However, if we are allowed to make some assumption, it can be solved in O(1) time. To do it, the strictures the list points to must be copyable. The algorithm is as the following:

We have a list looking like: … -> Node(i-1) -> Node(i) -> Node(i+1) -> … and we need to delete Node(i).

  1. Copy data (not pointer, the data itself) from Node(i+1) to Node(i), the list will look like: … -> Node(i-1) -> Node(i+1) -> Node(i+1) -> …
  2. Copy the NEXT of second Node(i+1) into a temporary variable.
  3. Now Delete the second Node(i+1), it doesn’t require pointer to the previous node.

Pseudocode:

void delete_node(Node* pNode)
{
    pNode->Data = pNode->Next->Data;  // Assume that SData::operator=(SData&) exists.
    Node* pTemp = pNode->Next->Next;
    delete(pNode->Next);
    pNode->Next = pTemp;
}

Mike.

More Related Contents:

  1. How to reverse a singly linked list using only two pointers?
  2. Merging two sorted linked lists
  3. Assorting linked list in c [duplicate]
  4. Recursive and non-recursive traversal of three degree tree
  5. I wrote this method to delete duplicate elements of a linked list, but it shows segmentation fault, why? [closed]
  6. Debugging a linked-list
  7. Please help me out, i want to display the linked list, reverse it & display then again display it
  8. How are multi-dimensional arrays formatted in memory?
  9. When should I use a List vs a LinkedList
  10. Is using flexible array members in C bad practice?
  11. What is the reason for using a double pointer when adding a node in a linked list?
  12. Quick Way to Implement Dictionary in C
  13. Using pointers to remove item from singly-linked list
  14. Relative performance of std::vector vs. std::list vs. std::slist?
  15. How do you implement a circular buffer in C?
  16. Problems with character input using scanf()
  17. C – How to implement Set data structure?
  18. Good STL-like library for C [closed]
  19. Rationale behind the container_of macro in linux/list.h
  20. adding list items or nodes in linked list
  21. What is a hash table and how do you make it in C? [closed]
  22. Linked list recursive reverse
  23. Implementing a HashMap in C [closed]
  24. Finding the intersecting node from two intersecting linked lists
  25. Sorting a linked list
  26. Does C have any tools for doing string addition?
  27. C: How to free nodes in the linked list?
  28. Automated field re-ordering in C structs to avoid padding
  29. How to implement a linked list in C?
  30. Standard data structure library in C? [closed]

Leave a Comment