# Question about singly linked lists

• AcecA
In summary, the conversation discusses using pseudocode and C pointer notation to remove an element from a linked list. It covers the potential issues with using pointer arithmetic and the importance of maintaining a pointer to the previous element in the list.

#### AcecA

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.

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:

## 1. What is a singly linked list and how does it work?

A singly linked list is a type of data structure that stores a collection of elements in a linear fashion. It consists of nodes that are linked together using pointers, with each node containing a data value and a pointer to the next node in the list. This allows for efficient insertion and deletion of elements, but accessing elements in the middle of the list can be time-consuming.

## 2. What is the difference between a singly linked list and a doubly linked list?

In a singly linked list, each node only has a pointer to the next node in the list. In a doubly linked list, each node has a pointer to both the next and previous nodes in the list. This allows for more efficient traversal in both directions, but it also requires more memory.

## 3. How do you insert an element at the beginning of a singly linked list?

To insert an element at the beginning of a singly linked list, you first create a new node with the desired data value. Then, you set the new node's pointer to point to the current head node, and update the head pointer to point to the new node. This effectively inserts the new node at the beginning of the list.

## 4. How do you delete an element from a singly linked list?

To delete an element from a singly linked list, you first need to find the node that contains the element you want to delete. Then, you update the pointer of the previous node to point to the node after the one you want to delete, and free the memory of the deleted node.

## 5. What is the time complexity of searching in a singly linked list?

The time complexity of searching in a singly linked list is O(n), where n is the number of elements in the list. This is because you have to traverse through the list, one node at a time, until you find the desired element.