Clever Geek Handbook

How do I change the items in the list?

I am trying to learn about data structures and algorithms myself. I wrote my own double list in C and now I want to write some algorithms to execute on the list. What is the preferred way to replace list items? Is it better to change the content or rearrange the pointers to the next and previous list item?

+2


source to share


5 answers


Rearrange pointers. Side effects can occur when replacing items. In particular, you can store a reference to a node somewhere outside of the function, and generally, when you change the order of the nodes in the list, you don't want people who have a reference to a node to suddenly find that the node is pointing to new data. This is because, in general, an important identifying characteristic of a node is the data that it points to a different position in the list.



+9


source


The canonical exchange is done through pointer permutation, has no side effects and is of course faster:



void swap (node *a, node *b) {
    node *tmp;

    tmp = a;
    a = b;
    b = tmp;
}
0


source


Depending on the type of content stored in the elements of the linked list, replacing the actual content of the element will be tricky (think of a linked list of length strings, for example), so it is easier to swap pointers that point to the next and previous elements in the list.

0


source


Depends on how you highlight the content.

If you keep a pointer to the content, then the content switching doesn't really matter. If you have a large structure that is part of your node, then switching pointers can be more efficient than copying the entire content.

0


source


I am leaning towards what most people have already said. A little background will likely help: pointer switches are guaranteed to work, whereas object exchange may not always be as easy as it sounds. Think about temporary ones that can / will be thrown and exceptions (and I mean in general, not as a C ++ language) can occur and actually leave your container (list) in an undesirable state. Look for invariants in your container - this is that the swap should leave the list size intact, as well as the items intact and styled on it.

0


source






More articles:


All Articles