Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Question about singly linked lists

  1. Mar 15, 2010 #1
    If you have a pointer that's pointing to one element in a list, can you do the following

    (*biggestPtr-1).next := biggestPtr+1

    This is pseudocode with := meaning the assignment operator.
  2. jcsd
  3. Mar 15, 2010 #2

    Filip Larsen

    User Avatar
    Gold Member

    It looks like you are using something similar to C pointer notation and I guess you would like to remove an element pointed to by p from the list by doing "*(p-1).next = p+1". If so, note that pointer arithmetic is similar to using array index, that is, p-1 points to the element in memory prior to p and this is in general not the same as the element prior to p in the linked list.

    In a single linked list where each element chain to the next, it is by definition not possible to find the element prior to an element directly from the element itself. You must maintain (or obtain by iteration from the head of the list) a pointer to the previous element separately and use that to unchain the element in question (with special care if the element to remove is the first element in the list).
  4. Mar 16, 2010 #3
    i assume bigestPtr is the size of your list.
    In this case the last Element of your list *(biggestPtr-1) points to an element that does not (yet) exist.
    This is no problem if you always check .next >= biggestPtr.
    And indeed the last element of the list cant have a valid next-pointer.
    But a reference to *(biggestPtr.next) might give a runtime error now, or produce random results.
    If biggestPtr is not the size of the list, but points to any other element. you have set (*biggestPtr-1).next to the next element in memory, which is not necessarily the next logical element of the list.
    Last edited: Mar 16, 2010
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook