Sign in to follow this  

lists and linked lists: what are they?

This topic is 4858 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

A linked list is a structure which consists of a string of nodes. Each node points to the node infront of it, and most of the time the one behind it aswell. This allows you to add new entries anywhere in the list without having to move everything else, like in an array. It also allows for very dynamic sizes, unlike arrays. The one thing that it doesn't do well is random access, which is what you use arrays for.

Share this post


Link to post
Share on other sites
You need to be careful here lists != linked-lists, a linked-list is just a specific dynamic data structure where as a list is an abstract data type (ADT) its a higher entity than a linked-list, what makes it an abstract type?

well the concept of a list is a "linear sequence of elements" from the statement it does not state that a specific data structure is needed, any date structure could be used to implement a list this is what makes it abstract because it can be implementated in more than one way, but the operations of a list are well defined and does not vary.

lists are usually implemenated with linked-lists (because they have the best all round trade-offs to make an efficent list) but they could just aswell be implemenated with an array but you need not concern yourself with these details you just care about what you can do with a list of something that is the operations of a list.

Share this post


Link to post
Share on other sites
That is a nice article. One benefit of STL linked lists over arrays is that when you have pointers that point to the nodes or elements of the list and you delete one element the pointers that pointed to other elements still work. However, when you remove an element from an array all the elements upstream of the deleted element are shifted down and thus pointers to them become invalid. Inserting elements in front of list is faster than for array. Finding element of a list is slow compared to the indexed element of an array. So each container has its advantages and disadvantages. I like STL containers because they abstract pointer usage and memory alloc/dealloc issues. I think I read somewhere how you can implement binary tree with arrays, fun stuff:)

Share this post


Link to post
Share on other sites
Link list is a data structure... that link to another data structur.

for ex:


struct number {

int num;
char str[255];
struct number * next;
};





next is the pointer to another struct address...
(to the same struct type...)

Share this post


Link to post
Share on other sites

This topic is 4858 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this