What is a practical use of a linked list?

[RedScare]

I have been reading up more and more on C, and it appears linked lists are very important in that language. Each time they are introduced, it is said they can be used as "stacks" or "queues" and are better at removing, adding, and inserting data members than arrays. But I have yet to think of or find a specific, non-contrived example where the benefit of access time for an array overshadows the extra time for insertion/deletion.

Furthermore, it seems that if I want to access data in a linked list, I must traverse it in order from start to finish; I can't say "pick element 'x'" or "pick the element with property 'y'" without testing every single element before the one I am looking for. Is this accurate?

Thank you very much for your time.

[Duthomhas]

Every structure has pros and cons.

A linked list is simply the way to manage unbounded memory. Additional constraints may be involved to make balanced trees or whatever, but ultimately its strength is that it has no memory limit.

A vector or array boasts access speed.

A deque combines the two.

A stack or queue can be built on top of any of these structures.

[helios]

What is a practical use of a linked list?

A queue for relatively large objects, such as a video's frames, or any queue that will be pushed by one thread and popped by another.
FAT uses linked lists as its directory structure.

[chrisname]

And Bash uses linked lists to store the arguments to a program (which end up in argv[])

[RedScare]

But vectors (and arrays that are frequently copied into larger ones depending on requirements) don't really have memory bounds either, right? Nothing (apart from efficiency concerns) stops a programmer from making an array a given minimum size and resizing it as need be by copying elements, correct? So don't vectors (or even properly managed arrays) give all the same benefits as a linked list without sacrificing random access efficiency?

It would appear that the only data that linked lists are suited for is specifically data that must be accessed in a specific order?

[chrisname]

No... you can't resize an array, but you can remove nodes from a linked list by freeing the memory they occupy and changing the pointer in the previous node.

Also a linked list can do this:

struct inode {
    size_t size;
    char* owner;
    void* blocklist;
    unsigned int inode_number;
    struct inode* next;
};

whereas each element of an array can only describe one thing, and only one datatype.

[Disch]

Nothing (apart from efficiency concerns) stops a programmer from making an array a given minimum size and resizing it as need be by copying elements, correct?

Emphasised for importance.

Increasing the size of a vector/array can be computationally expensive. It requires a large chunk of contiguous memory be allocated (in addition to to the original buffer).

For example if you're increasing from 100 bytes to 200 bytes in size, the computer actually needs 300 byte of memory available in order to increase the buffer size.

Then after the allocation, the entire array has to be copied to the new buffer. This can be expensive if it's done repeatedly. Even worse if the buffer size is substantailly large.

So don't vectors (or even properly managed arrays) give all the same benefits as a linked list without sacrificing random access efficiency?

Functionally you can do just about anything with a vector that you can do with a list... yes. But the difference is HOW they do it.

Lists can have elements easily inserted/removed anywhere, including at the front. Vectors cannot. Try to insert an element at the front of a vector and you probably have to reallocate/copy the entire array.


EDIT:

Here's a practial example. Say you have a game and you want to keep track of all enemies that are on screen. Some enemies fire bullets which you treat as normal enemies. When an enemy dies, it is removed from the group.

A list is more suitable here because:

- you don't need random access. Any operations you do to an enemy you'll probably be doing to the entire enemy group. Collision detection, for example... you'd have to check against every enemy to see if they collided. AI logic, etc. It all would be done on the group as a whole. Random access has no real value.

- the constant additions of new enemies (in the form of spawning, or bullets, or whathaveyou) might cause several reallocations/copies in a vector. But is no problem for a list.

- the constant removal of arbitrary enemies (upon their death) would require tons of object copying. If you're using a vector, everytime an enemy that isn't immediately at the end of the vector dies... all the enemies after it would have to be "shifted down" to fill the gap.


So yeah... if you need random access, you probably don't want a list. If you will be arbitrarily inserting/removing elements, you probably don't want a vector.

Different tools for different jobs.

[RedScare]

Thank you very much for the details. So are there any specific examples were data is only accessed in one order apart from file-system heirarchy and video frames? Are there any examples that relate to users, not to OS internals?

@chrisname: I think we have a misunderstanding; it is difficult to resize an array (as far as I know it's possible by dynamically creating the array and resizing it with realloc()), but it is possible to effectively resize it by copying it to an array of larger size and deleting the original.

[helios]

Are there any examples that relate to users

Huh? Are you a user or a programmer?

it is difficult to resize an array

It's not difficult. Any array can be "resized" by creating a larger one and copying the contents to the new one. It's just very expensive compared to a list. If the structure doesn't need random access, it's an unnecessary cost that can be avoided.

[RedScare]

@helios: I am a programmer, I meant that I was looking for examples in programs that are directly invoked by users (like text editors, calculators, etc) as opposed to OS-based examples like file systems and caches. About resizing an array, copying it to a larger array isn't resizing the same array; I think that what chrisname meant when he said resize, and what I mean when I say it, is resizing in place as far as is allowed by the given memory in a computer (realloc() will copy if there is not enough space, but using it is closer to an in-place resize than copying the complete contents of the array without checking for trailing usable space).

[chrisname]

I think we have a misunderstanding; it is difficult to resize an array (as far as I know it's possible by dynamically creating the array and resizing it with realloc())

Yes, you can allocate more memory to the pointer easily enough. The problem arises if you want to remove elements. The only way you can do that practically is by moving everything after the element you want to remove forward one. And then you have useless element at the end of the array.

but it is possible to effectively resize it by copying it to an array of larger size and deleting the original.

That's not resizing the array, that's making a new array, and like Disch said, if you wanted to make a 100 byte array into a 200 byte array, you'd use 300 bytes (100 of which are totally useless) to do it. It also requires a fair amount of CPU time, like helios and Disch both said.

[helios]

I meant that I was looking for examples in programs that are directly invoked by users

I did mention in my first post that they're used for frame queues. Such as the ones used in video and audio playback.

[chrisname]

Operating systems don't just occur. The user has about as much invovlement in invoking a userspace program as s/he does in invoking an operating system.
OS: the user powers the computer on, the BIOS performs some hardware initialization, POST routine, etc. and then reads the master/volume boot record of the boot media (depends on your CMOS settings). It fetches the bootloader from that media, loads it into memory, and then does a far jump to it's entry point. Then the bootloader loads the kernel and the kernel loads the rest of the operating system*...

Userspace program: same as the above, with the addition of the operating system reading the superblock/file allocation table of the file system and then finding the appropriate blocks to fetch from the volume, parsing the program's executable header and then mapping it into memory.

*Actually, Linux used to be loaded differently than that... a program called Loadlin would run within windows (pre NT) or DOS, load the Linux kernel into memory and then boot windows/DOS out of ring 0, and start executing. That's really mean, but pretty clever.

[Duthomhas]

A list also deals with memory fragmentation much better than a vector/array, and can allocate more data.