Linked Lists
Author
I'm Taking the www.cprogramming.com series of c++ tutorials, and up to now I have been doing completely fine. I just, however, took the tutorial on linked lists and almost ALL of it went over my head. Can anyone give me a better explanation, or at least tell me were i can get one?
In C++ there are no dynamic data types. For example, if you have an array, lets say in integer array 10 long, (int array[10];) once that array is created there is no way to adjust the size. Now lets say that the array is filled and sorted lowest to highest with these numbers: (-1 means that it is empty)
int array[10] = { 0, 1, 3, 4, 5, 6, -1, -1, -1, -1 };
and you want to insert 2 into the array and keep it sorted. The only way to do this is to move everything in the array from position 2 (array[2]) one position to the right. For a small array this is nice and simple, but if your array is very large, this can take a large amount of time.
With linked lists, to insert the number 2 into this "array" (i use "array" because it really is not an array) is easy. No moving or shifting of any numbers is required. All we do is take the NODE (these are an important concept in Linked Lists. A NODE is the data in the linked list that also contains a pointer to the NEXT item in the list {and in some cases the previous node, but that is doubly linked lists and that is another topic} )in the second position insert it with the NODE we are inserting (in this case '2') and then have the NODE with the '2' point to the NODE with the '3'. If you want a code sample respond and I can post one for you.
~guyaton
int array[10] = { 0, 1, 3, 4, 5, 6, -1, -1, -1, -1 };
and you want to insert 2 into the array and keep it sorted. The only way to do this is to move everything in the array from position 2 (array[2]) one position to the right. For a small array this is nice and simple, but if your array is very large, this can take a large amount of time.
With linked lists, to insert the number 2 into this "array" (i use "array" because it really is not an array) is easy. No moving or shifting of any numbers is required. All we do is take the NODE (these are an important concept in Linked Lists. A NODE is the data in the linked list that also contains a pointer to the NEXT item in the list {and in some cases the previous node, but that is doubly linked lists and that is another topic} )in the second position insert it with the NODE we are inserting (in this case '2') and then have the NODE with the '2' point to the NODE with the '3'. If you want a code sample respond and I can post one for you.
~guyaton
A linked list is a relatively simple way of storing multiple sets of data, like an array. The difference between an array and a linked list is that an array is random access (and generally static length, look up "dynamic arrays" if you want to have variable length arrays) and a linked list is sequential access. Compare an array to a CD and a linked list to a tape.
Linked lists can be constructed a number of ways but generally you have two parts to the structure: the actual list and an iterator.
Don't let's worry about how they work just yet, let's concentrate on what they are first.
Each instance in a list is usually called a node. In a singly linked list, each node has a pointer to the next node in the list as such:
Doubly linked lists have a pointer to the next and previous nodes in the list as such:
When you create a linked list, you create an empty node called the head node with null link pointers. Then when you want to add in a new item, you create it and point to it with the head's next pointer (also you point the new node's prev pointer to the head node). This continues for subsequent additions to the list.
This way we have created a list where each node contains a pointer to the next/previous node in the list.
Now for how this works.
The iterator is simply a pointer to a node:
// Linked list
Node LinkedList;
// Iterator
Node *pIterator;
Let's assume nodes have been added. To traverse the list we set this to the head pointer's address:
pIterator = &LinkedList
To traverse to the next item in the list, set the iterator to the next node pointer:
pIterator = pIterator->m_pNext;
Now the iterator points to the next node in the list.
Similarly:
pIterator = pIterator->m_pPrev;
will traverse back in a doubly linked list.
When pIterator->m_pPrev == 0, the iterator is pointing to the head node and when pIterator->m_pNext == 0, the iterator is pointing to the tail node.
That's the basic idea, you can create functions to wrap up this functionality and there are a number of deletion functions which I'm sure you'll find easy once you understand the general idea.
Note: The STL has a list variable type which can wrap up this functionality so you don't have to code it.
Linked lists can be constructed a number of ways but generally you have two parts to the structure: the actual list and an iterator.
Don't let's worry about how they work just yet, let's concentrate on what they are first.
Each instance in a list is usually called a node. In a singly linked list, each node has a pointer to the next node in the list as such:
class Node {public:// Methods and DataNode *m_pNext;}Doubly linked lists have a pointer to the next and previous nodes in the list as such:
class Node {public:// Methods and DataNode *m_pPrev;Node *m_pNext;}When you create a linked list, you create an empty node called the head node with null link pointers. Then when you want to add in a new item, you create it and point to it with the head's next pointer (also you point the new node's prev pointer to the head node). This continues for subsequent additions to the list.
This way we have created a list where each node contains a pointer to the next/previous node in the list.
Now for how this works.
The iterator is simply a pointer to a node:
// Linked list
Node LinkedList;
// Iterator
Node *pIterator;
Let's assume nodes have been added. To traverse the list we set this to the head pointer's address:
pIterator = &LinkedList
To traverse to the next item in the list, set the iterator to the next node pointer:
pIterator = pIterator->m_pNext;
Now the iterator points to the next node in the list.
Similarly:
pIterator = pIterator->m_pPrev;
will traverse back in a doubly linked list.
When pIterator->m_pPrev == 0, the iterator is pointing to the head node and when pIterator->m_pNext == 0, the iterator is pointing to the tail node.
That's the basic idea, you can create functions to wrap up this functionality and there are a number of deletion functions which I'm sure you'll find easy once you understand the general idea.
Note: The STL has a list variable type which can wrap up this functionality so you don't have to code it.
Quote:Original post by guyaton
In C++ there are no dynamic data types.
You mean data structures and/or abstract data types (ADTs), a linked list isn't a dynamic data type its a data structure and it isn't strictly true that C++ doesn't have ADTs either they are just not built in types. For example std::list is of course the List ADT and is implementated via a doubly linked-list data structure.
Quote:Original post by Leo_E_49
Compare an array to a CD and a linked list to a tape.
That is abit of an odd analogy that might be misleading [grin].
Quote:Original post by Leo_E_49
Linked lists can be constructed a number of ways but generally you have two parts to the structure: the actual list and an iterator.
I think you are mixing up lists and linked-lists, the former is an ADT the later is a specific data structure. Iterators are not the main concepts of linked-lists, i've never seen the definition of linked-lists refer to iterators (not that you can't have them).
The main component of a linked-list involves a self referential structure, in linked-list terminology this would be a node in a linked-list, the self reference conceptually represents a link to the next/previous node in a sequence of nodes, a node also contains an element.
Quote:Original post by Leo_E_49
The iterator is simply a pointer to a node:
That is not quite correct an Iterator is a concept, a list implementated with linked-list that has an iterator could certainly contain a linked-list node but a pointer to a node is not really an iterator.
I'm being picky because he's beginner so he should be told the correct terminology yada, yada for it.
The best analogy I can think of for linked lists is that really lame Michael Jackson video where all the people in the world are holding hands in a long line (GAG).
If you want to delete one person from that “list” of people, say Mr. Jackson him self, then you just join the hands of the two people he was holding together, then he can be safely deleted.
Lets say the list of people has a start person, and then the only thing that each person needs to remember is the Next person in the chain.
Class person {
Public:
Person *NextPerson;
}
The end of the chain of people is when a single person is not holding hands with some one to his / her right, or when NextPerson == NULL
If you want to delete one person from that “list” of people, say Mr. Jackson him self, then you just join the hands of the two people he was holding together, then he can be safely deleted.
Lets say the list of people has a start person, and then the only thing that each person needs to remember is the Next person in the chain.
Class person {
Public:
Person *NextPerson;
}
The end of the chain of people is when a single person is not holding hands with some one to his / her right, or when NextPerson == NULL
Quote:Original post by snk_kidQuote:Original post by Leo_E_49
Compare an array to a CD and a linked list to a tape.
That is abit of an odd analogy that might be misleading [grin].
I guess you're right there, but I couldn't think of a better one...
Quote:Original post by snk_kidQuote:Original post by Leo_E_49
Linked lists can be constructed a number of ways but generally you have two parts to the structure: the actual list and an iterator.
I think you are mixing up lists and linked-lists, the former is an ADT the later is a specific data structure. Iterators are not the main concepts of linked-lists, i've never seen the definition of linked-lists refer to iterators (not that you can't have them).
The main component of a linked-list involves a self referential structure, in linked-list terminology this would be a node in a linked-list, the self reference conceptually represents a link to the next/previous node in a sequence of nodes, a node also contains an element.
I'm not really talking theory wise here. He is a beginner after all and the theory is described quite well in his article. I'm providing an implementation which is simple and commonly used for his scrutiny. I do believe the STL implementation of linked lists uses an iterator concept, albeit more complex than mine, being a contained type declared within the list class which must be created with reference to the list structure's scope.
I find that using an iterator simplifies functionality somewhat. Also, your description of the actual list is identical to mine, although worded differently.
Quote:Original post by snk_kidQuote:Original post by Leo_E_49
The iterator is simply a pointer to a node:
That is not quite correct an Iterator is a concept, a list implementated with linked-list that has an iterator could certainly contain a linked-list node but a pointer to a node is not really an iterator.
True, but I was referring to my iterator concept. An iterator, no matter the structure, must contain a pointer to a node somewhere in it otherwise it cannot access the list. Using data copies of the list is costly in terms of memory and accessing the list via references, instead of pointers, is clearly impossible because a reference is set on declaration and cannot "point" to a new instance after declaration.
Most of the problems here are symantic, I'm using terminology different from yours but trying to put across the same concepts. I had hoped not to bog a beginner down with such complex issues.
By the way, mike: linked lists are an important concept to understand, and writing your own will help you understand them (as well as giving you more practise with writing C++). Now here's the strange part: once you understand what they are and how they work, don't use your own. There are all sorts of useful data structures (including linked lists) in the standard library, and it's much better to use them than to use your own.
But it's still very important to understand what they are and how they work! It's still a very good idea to finish understanding them, and it couldn't hurt to write a simple linked list to cement your understanding.
But it's still very important to understand what they are and how they work! It's still a very good idea to finish understanding them, and it couldn't hurt to write a simple linked list to cement your understanding.
As a beginner i dont think core explanation is the key. This is going off the way i learn of course, i learn through example so i first need to see it working before i start to look at the definition, going into the core definition of a linked list will scare the guy, although at some point you will have to learn all this to become a good programmer, so its a case of get it out of the way now or build into it . . . i personally would say build into it. Dont worry about linked lists too much yet just understand basically what a linked list is . . . basically a list, the word 'linked' to me just makes me think of chain links, they can be broken and reattached but they need to know where to be attached. If you are brand new to programming stay away from the dynamic side of things and just first get to grips with basic stuctures. As a learner it wont scare you. When you fully understand types, structures and a few algorithms and classes, then moe onto the advanced so to speak stuff.
this is just the way i travelled through programming, and i have to say when i talk to people who have ben doing it much longer than me, their talk is far from easy to undertstand and i start to feel hopeless
anyways, beeing a really code coder takles time and a lot of hard work
this is just the way i travelled through programming, and i have to say when i talk to people who have ben doing it much longer than me, their talk is far from easy to undertstand and i start to feel hopeless
anyways, beeing a really code coder takles time and a lot of hard work
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
