i dont get it, i really dont see the use at ALL in linked lists. i have read the chapter 15 on the site on them, and understand it. i just need to know why would you ever use them?
i dont get it, i really dont see the use at ALL in linked lists. i have read the chapter 15 on the site on them, and understand it. i just need to know why would you ever use them?
How would you read and store all the lines of a text file?
Lists are useful when you don't know in advance how many "somethings" (eg. lines from a file) you need to cope with.
Sure you could have
char *lines[1000000];
but that wastes a lot of space for small files, and doesn't work at all well for very large files.
But a linked list of lines neither wastes any memory on small files, and is only limited by the physical memory you have available.
If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
If at first you don't succeed, try writing your phone number on the exam paper.
If you haven't yet, read a tutorial on using something called a <vector>. It is just like an array, but it is much easier to use than an array: you can add or subtract more items at will, you can insert() items or erase() items, and you can sort() the items, etc. Behind the scenes, <vector>'s are implemented as linked lists.i dont get it, i really dont see the use at ALL in linked lists.
Last edited by 7stud; 02-25-2005 at 10:20 AM.
linked lists rule when you have many insertions or deletions.
in a linked list: simply unchain the element you want to remove or link the element you want to insert. its just setting a few pointers.
vectors: inserting an element: resize the vector, shift all elements past the index where you want to insert to the the end by the size of what you want to insert.
that means: if you insert at the beginning you need to shift ALL elements...
linked lists have the problem that they cant be accesses randomly (access at beginning or end: constant time, access anywhere else: linear time)
the advantage is: if you know youre going to insert an element next to a node you already know (e.g. you stored a pointer to it (e.g. head)) then insertion and deletion works in constant time.
signature under construction
std::vector isn't allowed to be implemented as a linked list - it's required to have contiguous memory.
just to get this straight:
vectors and linked list (and maps and sets) are CONTAINERS.
by convention all containers must provide methods to insert, delete, and lookup element.
even though the interface of all containers is the same (and you can do the same stuff with them) the complexity (= how many steps (e.g. instructions, comparisions) are required to get the the desired result) of the same method differs between the implementations of the containers.
looking up an element in a set can be done in O(log(n)) time (that means if there are n elements in the container, a lookup can be done with "only" log(n) comparissions)
that is because elements in a set are kept in a sorted order - thus a binary search can be done (note that set and map use red/black trees internally - thus even insertion and deletion can be done in O(log(n)) time)
looking up in a vector or linked list takes O(n) time (meaning if there are n elements youd have to check n elements) since you need to check every element if its the desired one.
so the basic idea of having different implementations of containers is to increase performance.
for more information on the stl:
http://www.sgi.com/tech/stl/
signature under construction
If you were writing a video editing program, you could use a linked list. Each video-frame could be an element in a linked-list. You want to insert and delete frames while keeping all of the other frames in order. You don't care as much about the absolute frame-number, as the relative position... Move ahead 10 frames... move back 10 frames, etc.