Linked lists (c++)

[Zacariaz]

I have tryed again and again understanding the use of linked lists, but i have failed.
Sure i understand the basics of how they work and how to use them, but i fail to see the benefits.

Obiously im missing something here, so i was thinking if any of you sdmart guys would be able to explain, in an "easy to understand way" what all the fuzz is about.

Thanks

[AJ]

Hi,

I don't think there is anything magic about linked lists

They basically allow you to allocate "array" elements without having contiguous memory to do so. Of course, in c++ the 'magic' is that template classes allow you to create linked lists without duplicating too much code.

Cheers,
Adam

[os64dev]

The benefits of a single linked list is also somewhat obscure to me. Double linked list on the other hand is less obscure because it's easy to understand. You could build a GUI using Double Linked list for instance a window has 1 or more children and the order in which the children are drawn can be important. A double linked list is easy here because you can traverse forward and backward through the children (think tab and shift-tab in windows).

In most cases to build dynamically size lists, a double linked list is easiest to implement. If you want performance then AVL trees, binary trees etc are better. In C++ if you have template based AVL trees or binary trees then it also fast to develop those lists.

[B.E]

I have tryed again and again understanding the use of linked lists, but i have failed.
Sure i understand the basics of how they work and how to use them, but i fail to see the benefits.

Obiously im missing something here, so i was thinking if any of you sdmart guys would be able to explain, in an "easy to understand way" what all the fuzz is about.

Thanks

the main benfit is that the memory or list can be resized without having to copy the old data to the new location (save time). also because the list isn't don't have to be continious, a items can be added or expanded, reordered (i.e sorting) without the moving the data or any other data (think about how would a word processor work, and how it would allow you to add, remove or change the contents of the file).

[deadmutex]

A linked list allows you to dynamically store data in a simple manner. In contrast, arrays let you store data, but they are usually static and they don't allow you to change their size once they're created. Adding/deleting new elements to the head or tail of a linked list is fast( O(1) ). Searching however is not efficient. You may have to search the entire list before you find what you're looking for( O(n) ).

You can use linked lists to implement a FIFO queue, where you enqueue to the head and dequeue from the tail. You can also use LLs to implement a LIFO stack.

[eboyd]

I don't really know what you could define as a "Linked-List". Is it a singly-linked list? a doubly-linked, circular, a binary tree, etc, etc, etc.

To me, a linked-list is any ADT "linked" together through the use of pointers.

If I were you, I wouldn't worry so much about the finer points of a linked list, but worry about creating your own ADTs
This is the basic idea behind most linkable ADTs:

Code: Select all

class node{
    
    protected:  // private if no inheritance scheme

        /*    Your private member data...
        */
        node* next;
        node* prev;
        node* wherever;

    public:

        /*    Constructors/Assignment Handling
        */
        node():next(NULL),prev(NULL),wherever(NULL){}
        node(const node& src):
                 next(src.next),prev(src.prev),wherever(src.wherever){}
       ~node(){}
        node& operator=(const node& src){
                 if(this != &src){
                     node* temp1, temp2, temp3;
                     try{
                         temp1 = new node(*src.next);
                         temp2 = new node(*src.prev);
                         temp3 = new node(*src.wherever);
                     }
                     catch(...){
                         delete temp1, temp2, temp3;
                         throw;
                     }
                     delete next, prev, wherever;
                     temp1 = src.next;
                     temp2 = src.prev;
                     temp3 = src.wherever;
                 } 
                 return *this;
               }

        /*    Accessors
        */
        node* get_next(){ return next; }
        node* get_prev(){ return prev; }
        node* get_wherever(){ return wherever; }

        /*    Mutators
        */
        void set_next(node* n){ next = n; }
        void set_prev(node* p){ prev = p; }
        void set_wherever(node* w){ wherever = w; }
};
       

So what's the benefit of all that code up there? Well I'm sure you've heard of the "array problem" and how inefficient it is to add/remove cells from an array when a linked-list can do it very efficiently.

For example, what happens if for years now some piece of code has used an array to store up to 1000 different items, and then one day, the world gets turned upside down and you need to delete 500 of your entries and add another 2000? Guess who'll will have to go in and re-write the code? me and you.

So if I write the list correctly, it won't matter if I have one entry or a million. The linked-list can handle it. Not to mention how MUCH EASIER the list operations are versus an array:

Code: Select all

myList->remove(5);
myList->insert(3);

myList->popFront();
myList->pushBack(217);

etc, etc, etc.

It's just so neat looking in main() now, thanks to that clean looking code!

[Kevin McGuire]

[a,c,b,e,d]

If each entry is 64 bytes and stored in an array. You wish to sort their order. You have to make two 64 byte copies. Copy c to a temp location then b to c's location.. ect.

[a]->[c]->->[e]->[d]

Here you just copy c's one (or two pointers for a double linked list) into a temp location, then copy b's pointers to c's, and finally copy c's from the temp location into b's. This means you only make two eight byte copies for a double linked list or two four byte copies for a single linked list which is much faster than copying the one hundred and twenty eight bytes.

It would make storing a list of structures which are different sizes easier.

It makes adding more items easier since you do not have to have a contiguous area of memory as is the case with a array.

A linked list is also a tree since each entry can point to multiple other entires like the trunk of a tree having many branches and so forth. This is more complicated to do with an contiguous array.

A linked list might not help with cache locality or having the smallest possible memory footprint versus a array.

[DeletedAccount]

Linked Lists
--------------
Consider this situation .. , you are given an assignment to
write an address book manager program ... If you use
and array you will declare an array like this struct
Address addresBook[MAX]; ... when you declare
like this you are actually wasting a lot of space ....when
you are not using most of the variables ... You might
argue that i will declare struct Address *p; and use
a combination of malloc () and relloc() function ...
But that is somewhat suboptimal .. You want to
write good programs right???

The best approach is in using a dynamic data structure
that grows in size as per the need's .. Lisked list is just
one of them .. Let me illustrate concept of linked list....
Consider a set boys going into a crowd .. The teacher
wants to keep track of them .. The teaches comes up with
a bright plan ... She assigns each boy a number and gives
him a token having the number of the next boy.By just
keeping track of the first boy .. she can keep track of
the entire set .. This is precisely what a linked is ......

Implementation
------------------
Let's implement a simple stack for that matter:
with operations push and pop

/*
this is a self referencial structure , the basic unit of
dynamic data structures......... consider it
as some thing like... [data]->


*/
struct list
{
int info;
struct list *next;
};
typedef list* LIST_PTR;

/*initializes a linked list*/
void init_node(LIST_PTR *p)
{
*p = NULL;

}/*
allocates memory

*/
LIST_PTR get_node()
{
LIST_PTR p =(LIST_PTR)malloc(sizeof(LIST_PTR));
p->next = NULL;
return p;
}
/*
push () :- inserts a data at top of stack
*/
void push(LIST_PTR *p,int data)
{
LIST_PTR temp = get_node();
temp->info = data;
temp->next = NULL;
if(*p == NULL)
{
*p =temp;
}
else
{
temp->next = *p;
*p=temp;
}
}
/*pops from stack*/
int pop(LIST_PTR *p)
{

int ret;
LIST_PTR temp = *p;
if(*p == NULL)
return -1;
ret = (*p)->info;
*p = (*p)->next;

free(temp);
return ret;
}
/*void display .. just display it*/
void display(LIST_PTR *p)
{
if(*p == NULL)
return;
else
{
printf("%d",(*p)->info);
display((*p)->next);
}
}

hope this clarifies a bit ....

[Zacariaz]

thank you very much, i actually have got a pretty good understanding of the subject, although contructiong more... exotic linked lists like double linked or multidimensional, still proves hard.

Anyhow, i do have one last question which i think is best asked by a short example:

Code: Select all

struct node {node *next;};
int main() {
  node *root = new node;
  root->next = root;
  /* it doesnt get simpler or anymore useless
     than this, but allthough this describes
     a single node which contains no data and
     links only to it self, it should qualify
     as a linked list. And now the question */
  root = 0;
  /* OR */
  root = new node;
  /* obiously will result in loss of the
     linked list which "root" was the only
     pointer keeping track on, but what
     really happens, is the memory now free,
     will other variables and stuff be able
     to, later on in the program, use parts of
    the memory formerly occupied by the list? */
}

[DeletedAccount]

This is the classic example of a memory leak ... what happens here
is that since you have already allocated memory and do not have
anything "pointing to it" :- that memory remains allocated and still
cannot be used by ur program using "normal ways"... Best practice
is to do something like this
node *temp = root;
root = new node;
free(temp); // or delete temp;

[DeletedAccount]

just take your time to get used to concept of a self referencial structure....
at this level .. think of everything from an abstract plane ... Then everything
will be clear .. You will have to power to make any dynamic data structure
you want....

[Zacariaz]

the memory thingy is just a tine part of my laking skills, but you discribe free() and delete, what is the diference really? allso in the case you discribe both "root" and "temp" points to the list, does it matter which one you delete or should you maybe delete both? what is the correct way?

I assume that it is important to delete the root it self anyway, fx.

Code: Select all

node *root = new node;
node *temp = root
temp->next = new node;
temp = temp->next;

delete root; // would be the corect way as it deletes the entire list
delete temp; /* would be wrong as there excists no links to the previous part of the list, thus the whole list wouldnt be deleted, however this fact could be used on purpose to delete only part of the list */

am i right in assuming this?

Thanks alot by the way.

[DeletedAccount]

Hi man,
One of the basic differences between free and delete is that free ()
will not call the destructor and delete does call the destructor of
the class . Okay thats. . that....

Now for the second part.....
I was just demonstrating how to free a single node ... not just the entire
linked list . For deleting the entire block linked list you show iterate
over each field and delete nodes seperately .. like this

while(root != NULL)
{
NODE *temp = root;
delete temp;
root=root->next;
}

You should not that when you use new on an already allocated
object ... The already allocated momory remains there till the
death of the program.... Also try to learn how to use gdb ...
this help you understand the differnce between "what you
wanted to do" and "what your program does"

[Zacariaz]

well thanks for all, youve been a great help.

[Zacariaz]

and the questions keep on comming...

Code: Select all

#include <iostream>
struct node {
  int val;
  node *next;
};
int main() {

  // i start out by creating "wrapping" list.
  node *root = new node;
  node *temp = root;
  root->val = 0;
  for(int n = 1; n < 4; n++) {
    temp->next = new node;
    temp = temp->next;
    temp->val = n;
  }
  temp->next = root;
  temp = root;

  /* then i test if it works, and it does, atleast for me, i have had some
     trouble in my attemps to make lists like this one, and it is possible
     that it works only by accident. */
  for(int n = 0; n < 16; n++) {
    std::cout << temp->val << std::endl;
    temp = temp->next;
  }
  std::cin.get();
}

Now the question is if theres anyway to count the nodes in a list like this? i mean there is no NULL pointer or anything, is it necacery to assing an unique ID to each node or something simular?.
allso i have experience that you can do stuff like:
root->next->next->next->next->val;
but again ive had some trouble with it and would like to know if it "legal" and safe;