Question about singly linked lists

  • Thread starter Thread starter AcecA
  • Start date Start date
Click For Summary
Pointer arithmetic in linked lists can lead to confusion, particularly when attempting to manipulate elements directly. The pseudocode presented suggests removing an element from a linked list using pointer arithmetic, but this approach is flawed. In a singly linked list, each node only contains a reference to the next node, making it impossible to access the previous node directly from the current node. Therefore, to remove an element, a separate pointer to the previous node must be maintained. Additionally, the concept of using pointers to navigate memory can result in errors if not carefully managed, especially if the pointers do not correspond to valid elements in the list. The last element in the list will not have a valid next pointer, which can lead to runtime errors or undefined behavior if not properly handled. Overall, manipulating linked lists requires a clear understanding of their structure and careful pointer management to avoid errors.
AcecA
Messages
12
Reaction score
0
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.
 
Technology news on Phys.org
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).
 
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 can't 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:
Learn If you want to write code for Python Machine learning, AI Statistics/data analysis Scientific research Web application servers Some microcontrollers JavaScript/Node JS/TypeScript Web sites Web application servers C# Games (Unity) Consumer applications (Windows) Business applications C++ Games (Unreal Engine) Operating systems, device drivers Microcontrollers/embedded systems Consumer applications (Linux) Some more tips: Do not learn C++ (or any other dialect of C) as a...

Similar threads

  • · Replies 40 ·
2
Replies
40
Views
977
  • · Replies 16 ·
Replies
16
Views
3K
Replies
86
Views
2K
  • · Replies 2 ·
Replies
2
Views
1K
  • · Replies 4 ·
Replies
4
Views
2K
  • · Replies 8 ·
Replies
8
Views
2K
  • · Replies 20 ·
Replies
20
Views
6K
  • · Replies 7 ·
Replies
7
Views
2K
  • · Replies 3 ·
Replies
3
Views
2K
  • · Replies 2 ·
Replies
2
Views
2K