Win a copy of Kotlin in Action this week in the Kotlin forum!
  • Post Reply Bookmark Topic Watch Topic
  • New Topic

Get reference to previous node in a singly linked list  RSS feed

 
Ioannis Michailidis
Greenhorn
Posts: 7
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi there,

i have the following graph in the Adjacent List representation and want to write a remove() method to it (have already unsuccessfully started).



Wenn I iterate over the elements of my list to find the node which needs to be removed, with the help of AdjLinkedList, I get a pointer to the current element. But I want a pointer to the previous node, so that I can set its internal pointer to the originally next node of the one which needs to be removed. Is there an easy way to do that, or do I have to change my Iterator class in order to keep a pointer also to the previous node?

Thanks in advance.
ioannis
 
Campbell Ritchie
Marshal
Posts: 55748
163
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
You cannot simply go to the previous node in a singly‑linked list. You would have to create a doubly‑linked list, or an array list, or have your Iterator retain the pointer to the previous node.
 
Ioannis Michailidis
Greenhorn
Posts: 7
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thank you for your quick response.

I have been thinking that, since I am iterating my list from the beginning, I had the reference I wanted at some point. If i could therefore check in each step the next reference against the value i am interested in, I would exit the loop. I tried



to use from for this purpose, but by calling again adjList.next(); in the loop, I mess with the iteration process. Is there a way to get from at each step, and at the same time iterate correctly?

ioannis

 
Campbell Ritchie
Marshal
Posts: 55748
163
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I am afraid that code shows the hazards of poor naming. Things like e.w are impossible to understand. That is why you shou‍ld always give variables meaningful names. It also does not show which class the remove method is in. It shou‍ld be in whichever class models the path, so it can take care of itself. Also you shou‍ld give fields private access (except for global constants), so things like e.w might fail to compile. Also look at our style suggestions about spacing; you shou‍ld put more spaces in the heading of your for loop.
Maybe each Edge shou‍ld keep a reference to its start and finish nodes, or maybe you shou‍ld use a different type of List. Why are you using a singly‑linked list?
Are you deleting all the nodes from position n ot the end? If so, can you simply delete node n (=set next to null in n − 1) and let the rest of the list become unreachable and eligible for garbage collection?
 
Ioannis Michailidis
Greenhorn
Posts: 7
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
The idea was to pass each time a new Edge to the remove() method,



which would keep references to the start and end nodes (remove(new Edge)) needed to be deleted from the SparseGraph (the whole class in which remove() is also included, is in my first post).

Insert(), as you can see is implemented in constant time, always at the beginning of the list. For remove, I have to iterate the list at the position of the start node of the edge to be deleted, find the end node of this edge, and then link the previous with the next node. I had the impression, that a singly linked list would do, but it seems I am not getting a clear iteration...

Best Regards
ioannis
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!