Singly linked lists - what are they for?
I just read through a tutorial here:
http://www.cprogramming.com/tutorial/lesson15.html
i think i more or less understood how it works but i can not think of a situation where this is usefull?
what are linked lists good for - when are they used?
thanks in advance
http://www.cprogramming.com/tutorial/lesson15.html
i think i more or less understood how it works but i can not think of a situation where this is usefull?
what are linked lists good for - when are they used?
thanks in advance
(Single) linked lists are extremely efficient in specific situations. For instance, they can Add/Delete a (non-first/last) element in constant time (simply 'repoint' *next), while allowing for flexible list sizes. An example might clear this up:
Consider the elements [5, 8, 3, 4], where the sequence is important. Using a linked list, I can add an element anywhere I like: if I want to add '6' between '8' and '3' I simply put 8->next = 6 and 6->next = 3.
If I wanted to do the same with an array, I'd need to copy 3 and 4 to the next 'index' and set then set the old location of 3 to 6. Additionally, I would need to be sure that the array size is >= 5, else we'll simply lose '4' because there is no place left to copy it to.
The same goes for Deleting elements, except that with an array, you're now stuck with a doubled value at the end (Delete(8) -> 3 is copied to the location of 8, 4 is copied to the location of 3, the location of 4 remains 4).
The downsides are:
a) One-way traversing (solved by doubly linked lists, which keep a *next and *prev).
b) No random access (To get to 3, I need to ->next until I find it, even if I know which location it is saved at! In contrast, an array value can be accessed by array[i]).
[edit]
A small example where it can be used:
I once made a "game" (actually, a tool to track a real-life game) where people had to do actions in a fixed sequence. Under certain circumstances, a person could "quit" or "join" during the cycle. Thus, after each action, the program would ->next to see who's turn it is, then see if he had to quit (Delete player by changing ->next pointers) or if someone had joined.
A singly linked list was perfect for this because a) action sequences were fixed and unidirectional, b) players could quit or join at any moment and c) "random access" was faked by means of asyncronous updates (i.e. remember who quits and who joins at which location, then update when that person or location is reached, rather than waste time with finding the location and updating immediately).
Consider the elements [5, 8, 3, 4], where the sequence is important. Using a linked list, I can add an element anywhere I like: if I want to add '6' between '8' and '3' I simply put 8->next = 6 and 6->next = 3.
If I wanted to do the same with an array, I'd need to copy 3 and 4 to the next 'index' and set then set the old location of 3 to 6. Additionally, I would need to be sure that the array size is >= 5, else we'll simply lose '4' because there is no place left to copy it to.
The same goes for Deleting elements, except that with an array, you're now stuck with a doubled value at the end (Delete(8) -> 3 is copied to the location of 8, 4 is copied to the location of 3, the location of 4 remains 4).
The downsides are:
a) One-way traversing (solved by doubly linked lists, which keep a *next and *prev).
b) No random access (To get to 3, I need to ->next until I find it, even if I know which location it is saved at! In contrast, an array value can be accessed by array[i]).
[edit]
A small example where it can be used:
I once made a "game" (actually, a tool to track a real-life game) where people had to do actions in a fixed sequence. Under certain circumstances, a person could "quit" or "join" during the cycle. Thus, after each action, the program would ->next to see who's turn it is, then see if he had to quit (Delete player by changing ->next pointers) or if someone had joined.
A singly linked list was perfect for this because a) action sequences were fixed and unidirectional, b) players could quit or join at any moment and c) "random access" was faked by means of asyncronous updates (i.e. remember who quits and who joins at which location, then update when that person or location is reached, rather than waste time with finding the location and updating immediately).
Last edited on
Topic archived. No new replies allowed.