C++ linked lists

[mkrohn]

I'm in a C programming class and we've reached chapter 17 and its linked lists. I got into a bit of an argument with the instructor today because linked lists are really quite hard and confusing for seemingly no reason at all. I completely get arrays and structures and those are useful. Vectors can do the same job of linked lists. Anything large enough to justify going to linked lists wouldn't it justify using a DB instead? I have a quiz on wednesday and I can't learn something that I can't understand a valid application of.

Can somebody help me out? I did the HW for this chapter but it was mostly the puke crap out through copy/paste. I don't have an actual understanding of it.

 

[Digital Viper-X-]

Linked lists have a few "pros" against say arrays.

No fixed size, no fixed length, re-organizing is easier and less memory intensive.

It's literally been years since I've touched LL so I may be out of date or remember things incorrectly.

Just be patient and it will come, start with the basics of a linked list, even the wiki page is useful.

http://en.wikipedia.org/wiki/Linked_list

 

[serpretetsky]

Anything large enough to justify going to linked lists wouldn't it justify using a DB instead?

I don't think I've heard this term in my courses yet. DB as in database? Don't you still need to decide what structures to use for you database (linked lists, arrays, hash tables,...).

 

[mkrohn]

I don't think I've heard this term in my courses yet. DB as in database? Don't you still need to decide what structures to use for you database (linked lists, arrays, hash tables,...).

yeah things like Int, chars etc but a database is where you put any large amounts of data you plan to do anything with really. It handles large volumes of data in a way that is both easier and faster than things like a linked list would.

I have always been a web person and have done a ton of PHP/mySQL work so I'm used to just using a DB for sorting and so many other things so I may be a little "backwards" in C++ land which is why I'm asking questions which my teacher doesn't seem to have answers for. He gives me shit for liking Linux, PHP and the non MS stuff.

 

[wonderfield]

Anything large enough to justify going to linked lists wouldn't it justify using a DB instead?

But wouldn't you argue that's also the case for vectors? Vectors may exhibit better performance than linked lists, even for large numbers of elements, and even when you might expect linked lists to outperform a vector due to the complexity characteristics of operations in which lists excel.

Databases are wonderful things for persistent data, and certainly in cases where data persistence is required beyond application lifetime. But if data lifetime is relatively short (application lifetime or sub-application lifetime), an external database starts looking like something of a steamroller when all one really needs is a rolling pin. The STL certainly has no useless facilities that I've been able to come across.

Suffice it to say that linked lists (as a concept, if not an implementation itself) exist not only for the characteristics they offer that are unique to them, but also because linked lists are the foundation from which other types of containers are built.

 

[Justintoxicated]

But wouldn't you argue that's also the case for vectors? Vectors may exhibit better performance than linked lists, even for large numbers of elements, and even when you might expect linked lists to outperform a vector due to the complexity characteristics of operations in which lists excel.

Databases are wonderful things for persistent data, and certainly in cases where data persistence is required beyond application lifetime. But if data lifetime is relatively short (application lifetime or sub-application lifetime), an external database starts looking like something of a steamroller when all one really needs is a rolling pin. The STL certainly has no useless facilities that I've been able to come across.

Suffice it to say that linked lists (as a concept, if not an implementation itself) exist not only for the characteristics they offer that are unique to them, but also because linked lists are the foundation from which other types of containers are built.

I map lists of database objects to LinkedLists and ArrayLists all the time, so really you need both for their own purposes. It would be a transaction nightmare if you had to persist data every time you manipulate it in an array. I don't remember the core fundamentals of C++ and how vectors are different than arrays in C, but lists allow inheritance and polymorphism in Java. You can for example retrieve a List of objects (rather than an array), modify the contents of every object within that list, add or subtract nodes from the list, sort the list etc then persist the list back to the database quite easily with only a single transaction.

Imagine something on the front end of an application being modified by the user (needs to change size of the list add or subtract from it, maybe a dropdown or drag and drop type UI) then submit his finished results it to the backend to the DB to persist the changes. You don't necessarily want the user to create a transaction with every add or remove before they are ready to save the data or submit for form. You would need to generate temporary tables' on the fly, and what happens with when you have 100 potential users manipulating the list at the same time?

This also probably becomes more apparent once you have lists of objects that have lists of other objects that have lists of other object etc.

Were you dealing with simple Linked Lists or Double Linked Lists?

 

[Dogs]

I'm in a C programming class and we've reached chapter 17 and its linked lists. I got into a bit of an argument with the instructor today because linked lists are really quite hard and confusing for seemingly no reason at all.

There are two important ideas you need to understand in order to understand linked lists and their purpose. Pointers and complexity.

A linked list is sort of like a freight train, in some sense. It consists of 'nodes' chained together. Each node serves two purposes. One, it stores a value, and two, it points to the next node. If you had a linked list full of integers, it might look something like this:
[head]->[5]->[3]->[9]->[2]->[1]
...where each box ([]) is a chunk of memory. This is in comparison to an array, which would look more like this:
[5,3,9,2,1]

Now, we'll try to get to why this is important.

I completely get arrays and structures and those are useful. Vectors can do the same job of linked lists.

So you have a dynamic array with the values 5,3,9,2,1, like above. It looks like this:
[5,3,9,2,1]
...Now let's say you want to add the number 4 to the front of the list, I.E. create:
[4,3,9,2,1]
How would the system do this? The answer is not very ideal. You must find a new block of memory which can hold all 6 values, and then copy each value in one by one. Even if you get lucky and you can just increase the size of the current array by 1, you still need to shift every item down by 1. If you have 5 elements, this means roughly 5 steps. If you have 100 elements, this means roughly 100 steps. If you have 60,000,000,000,000 elements, this means roughly 60,000,000,000,000 steps. In other words, the complexity of adding a new element to a dynamic array grows linearly with the size of the array.

Now let's try the same thing with a linked list, which looks like this:
[head]->[5]->[3]->[9]->[2]->[1]
All we really have to do is create another node and copy a 4 into it, set its pointer to the node that was at the front (the one with the 5), and then set the head node to point at the node we just created.
[4] [head]->[5]->[3]->[9]->[2]->[1]
[head]-> [4] [5]->[3]->[9]->[2]->[1]
[head]->[4]->[5]->[3]->[9]->[2]->[1]

This only takes a few steps, regardless of how many items are in the list, be it 5 or 100 or 60,000,000,000,000. Similar things are true for deleting the first item, as well.

In addition, similar things happen with adding or deleting in the middle of the list. You do have to start at the head node and work your way to the part of the chain you're searching for, so they're not as fast as inserting at the front, but these types of operations are still generally faster than their array counterparts.

So to some degree, writing to a linked list is faster than writing to an array. On the other hand, though, we have to remember that reading from the dynamic array will be faster than reading from the linked list. If you want the 50th element of the linked-list, you have to start at the head node, and visit each node to get the pointer to the next node until you reach the 50th element. If you want to access the 50th element of the array, you just multiply the size of an element by the index you're trying to reach and add it as an offset to the base address. If an array of integers (4 bytes) starts at address 1200(base 10) and you want the 50th element, you know through simple arithmetic that the address is 1400(base 10). But since the memory layout for a linked list isn't contiguous, you have no way to calculate what address a given value will be at, so you have to visit every link in the chain until you reach the one you want.

So really, it's about how often you're going to be reading vs how often you're going to be writing.

Anything large enough to justify going to linked lists wouldn't it justify using a DB instead?

No, since whether or not a linked-list is a good approach depends on the types of operations you're doing moreso than the number of items.

Databases are written to be fast at large sets of data you're going to be doing a lot of 'set-based' operations on...you might be adding data to it fairly regularly, but the data is going to stay there for a while and you're usually going to be asking for large chunks of data at once, or searching for individual pieces of data based on a number of parameters about it. It's good for those types of tasks, but if you want something you can access quickly (databases can live in memory if they need to, but in 'large sets of data' type uses, the database is usually going to reside on a different host on the network, meaning there will be some network overhead) and make a lot of adds and deletes to, a linked-list is often a great choice.

Not every problem is going to be the archetypal situation for using a linked-list...I find myself using an std::vector far more than I do std::list. But there are situations where using a linked list is simply the best choice due to the nature of what you're doing to the data you're working with.

but also because linked lists are the foundation from which other types of containers are built.

This is a very important item to remember. Things like the B+ trees used in database indexes share a very strong resemblance to linked lists, structurally. If you can't figure out how a linked-list works, you won't be able to figure out how trees work, and if you can't figure out how trees work you're going to be putting yourself at a severe disadvantage when it comes to computer science. It's important to learn how linked-lists work so you can go on to learn about more complicated things like the chain of responsibility pattern, or abstract syntax trees. If you want to work with the cool things, like operating systems, compilers and databases, you have to understand the basics.

 

[wonderfield]

I don't remember the core fundamentals of C++ and how vectors are different than arrays in C

In C++, a std::vector is simply a wrapper around built-in arrays which provides automatic expansion. Built-in arrays and std::arrays are fixed in size, set either at compile-time (or at runtime with arrays of runtime bound).

In other words, the complexity of adding a new element to a dynamic array grows linearly with the size of the array.

To clarify this sentence very slightly, insertion at the non-end of a vector happens in linear time, but insertion at the end of (a correctly-implemented) std::vector happens in amortized constant time.

 

[drescherjm]

quite hard and confusing for seemingly no reason at all

Linked lists confusing? I have never thought that. Although I have not created one myself in 2 decades, I use lists frequently in my c++ code at least as frequently as vectors.

 

[hofan41]

yeah things like Int, chars etc but a database is where you put any large amounts of data you plan to do anything with really. It handles large volumes of data in a way that is both easier and faster than things like a linked list would.

a database is not a data structure, it is an application.

e.g. how do you implement a database in c++? more than likely it would involve using a data structure such as an array or a linked list, or both.

 

[LuminaryJanitor]

I got into a bit of an argument with the instructor today because linked lists are really quite hard and confusing for seemingly no reason at all. I completely get arrays and structures and those are useful. Vectors can do the same job of linked lists.

It's really pretty straightforward. Linked lists give you unlimited size and fast inserts/deletes, but accessing data takes time. Arrays allow fast lookups, but they have a fixed size.

Vectors provide inserts/deletes/resizing on arrays, but these operations are not cheap. If you're using them heavily, then a linked list may be much faster.

A simple queue is a good practical example. You add to the back; you remove from the front; you never, ever need to look in the middle. A doubly-linked list is a perfect fit. If you try to do this with a vector, then every single delete will (internally) copy the whole queue. By the time you've emptied a 10,000-item queue, you'll have copied fifty billion elements around for no good reason.

 

[Dogs]

Vectors provide inserts/deletes/resizing on arrays, but these operations are not cheap. If you're using them heavily, then a linked list may be much faster.

Right. When I briefly explored high-performance computer, we would always have to be careful using vectors. If you're adding a bunch of elements to a vector one at a time, you better anticipate at least a rough size and set the capacity accordingly, because every time you go over the capacity the vector has to stop, reallocate (to double its previous size) and go again. If you start from an empty vector and try to add 500,000 items, it's going to take an awful lot longer than if you've set the capacity to 500,000 before hand. The trouble shows up when you know the number of elements will be very large, but you have absolutely no way of determining how large that may be. If your algorithms are going to be moving sequentially through the list anyways, the areas where a vector is slow can be more costly than the areas where it is fast.

 

[Justintoxicated]

It's really pretty straightforward. Linked lists give you unlimited size and fast inserts/deletes, but accessing data takes time. Arrays allow fast lookups, but they have a fixed size.

Vectors provide inserts/deletes/resizing on arrays, but these operations are not cheap. If you're using them heavily, then a linked list may be much faster.

A simple queue is a good practical example. You add to the back; you remove from the front; you never, ever need to look in the middle. A doubly-linked list is a perfect fit. If you try to do this with a vector, then every single delete will (internally) copy the whole queue. By the time you've emptied a 10,000-item queue, you'll have copied fifty billion elements around for no good reason.

nice example, concise and to the point.

 

[BDV]

Linked lists are a good intro data structure that will help you understand stuff like Binary Trees, Graphs in the future.

They are also oftentimes used as parts of bigger data structures, i.e. Hashtables, due to their compactness and relative efficiency.

That being said, it is very unlikely that you'll use a linked list in your professional career

 

[jimmyb]

More answers please; I don't think we have enough.

 

[Dogs]

More answers please; I don't think we have enough.

Are you the kind of person who think's Google would be better if it only ever gave you 1 search result?

 

[jimmyb]

No.