Main:advertisement
Utilizing pointer concept to turn in to neat data structure...
/***************************************
Advance C++ concept
Linked List
by : Alka G Vulcan
email: ankiov.spetsnaz@gmail.com
***************************************/
<!-- Pre requisite --!>
*Basic understanding of C++
*Pointer (critical)
*Recursion (also critical)
*Concepts of structure and class
<!-- Intro --!>
As I've foreshadowed before, this time we are going to discuss about Link List. Some may argue Link List is better data type then Array, but that’s arguable.
Link List is similar to array, but while array is continuous block of memory, link list is simply a struct or class compose of data and pointer that points to next node. There for it’s much easier to delete, or add in the middle of data sequence. But it can’t jump like array. Array[3] will result 4 th element but link list will have to go through 1 st, 2 nd, and 3 rd element to get to 4 th element.
BTW, if you didn’t really play around a lot with pointer it can be very hard to understand….
<!-- Main --!>
Before we actually jump into codes, I would like to give you a picture. A good picture is worth 1000 words…
CODE
Array[5];
Looks like this in memory block.... i hope ya like my awesome paint skill...
http://img49.imageshack.us/img49/1039/arraymemoryblockqu4.th.jpg
As you can see we are assigned 5 continuous memory blocks.
But link list, will looks like this…. (2 nd block is pointer, arrow is indication where that pointer is pointing to)
http://img170.imageshack.us/img170/7136/linklistmemoryblockjo9.th.jpg
It has pointer that points to the next data. There for we can access the next data through that pointer, by doing so, it can work as if it’s continuous block of memory…
Now let me throw some code at you…. :D
I hope comments are self explanatory…
And I don’t know if you noticed or not, link list doesn’t have set amount of capacity. It grows and shrinks as we add or delete data, and it’s really easy to insert middle of the list unlike array. In order to insert data in the middle of array you would have to copy current data to temporary block of memory and resize capacity and copy temp to resized array, assuming you have max capacity array. While link list all you have to do is make new node and change pointers…
That’s why people may argue that it’s more efficient, but pure straight line link list isn’t that efficient at all because there isn’t really good algorithms for search, sort or anything… It’s inevitable(1) to have, at worst case, big O (n) for search, and
...............n
big O ( (sigma) n^i) would be algorithm for sort…. I think…. //ignore dots, needed since forum deletes space or tab... it's used to express summation algorithm
.............i = 0
(1) I say it’s inevitable because we can’t use effective array algorithm due to lack of bracket operators…. Since we would have to go to node before our target to actually know the address of our target… which mean we would have to visit every node before our target to get to our target….
<!—END --!>
I feel this is the sloppiest work I’ve ever done… but I really can’t think of better way to show it to you then source code…
I hope you see the pros and cons of link list, and you may decided cons of linklist is far greater then pros....
But imagine the case of Queue..... It's way easier to do it with queue since with array you would have some blank memory blocks at the beginning that is little tricky to manage, although possible and very fun to write code for it...
And as I've mentioned earlier.... there is way to make alternation to link list so it would be able to use better and faster algorithm.... like in my book word frequency counter program... when you use enhanced version of link list it's so much much faster...
I may write article about it later.... but I think my summer jobs gonna be awesome and really time consuming....
Also C++ have linked list implemented and you can utilized it by key word list just like vectors.... but best way to understand how it works is by making one...
Advance C++ concept
Linked List
by : Alka G Vulcan
email: ankiov.spetsnaz@gmail.com
***************************************/
<!-- Pre requisite --!>
*Basic understanding of C++
*Pointer (critical)
*Recursion (also critical)
*Concepts of structure and class
<!-- Intro --!>
As I've foreshadowed before, this time we are going to discuss about Link List. Some may argue Link List is better data type then Array, but that’s arguable.
Link List is similar to array, but while array is continuous block of memory, link list is simply a struct or class compose of data and pointer that points to next node. There for it’s much easier to delete, or add in the middle of data sequence. But it can’t jump like array. Array[3] will result 4 th element but link list will have to go through 1 st, 2 nd, and 3 rd element to get to 4 th element.
BTW, if you didn’t really play around a lot with pointer it can be very hard to understand….
<!-- Main --!>
Before we actually jump into codes, I would like to give you a picture. A good picture is worth 1000 words…
CODE
Array[5];
Looks like this in memory block.... i hope ya like my awesome paint skill...
http://img49.imageshack.us/img49/1039/arraymemoryblockqu4.th.jpg
As you can see we are assigned 5 continuous memory blocks.
But link list, will looks like this…. (2 nd block is pointer, arrow is indication where that pointer is pointing to)
http://img170.imageshack.us/img170/7136/linklistmemoryblockjo9.th.jpg
It has pointer that points to the next data. There for we can access the next data through that pointer, by doing so, it can work as if it’s continuous block of memory…
Now let me throw some code at you…. :D
class linkList
{
private :
struct node //structure within class, some may use class instead of struct and use friend of
// class thing but I like this way better… :P
{
int data; //actual data that we be concerning about
node *next; //node pointer to next
node(int d = 0, node *n = NULL) //node constructor, imperative to have NULL default value
{
data = d;
next =n;
}
};
node *head; //pointer to head, so we will always know where to start from
public :
linkList () {head = NULL;} //constructor, it is also imperative to point to null
void display(); //function displays its contents
void append(int); //append to end
void erase(int); //delete a matching node
~linkList(); //destructor
void insertNode(int v);
};
/*
It’s imperative to understand why we set pointer to NULL at very beginning.
Depends on compiler, when variable is created, it may be filled with random thrash. So if we don’t point it to NULL, it may be pointing to something else, it may be pointing to a very important data.
Also, otherwise there isn’t good way to figure out if we are at the end of list, while this method we can tell we are at the end of list if it's same as NULL...
*/
CODE
void linkList :: display()
{
node* start = head; //start from the head
while(start != NULL) //if it’s not set null, if it’s not the end of list
{
cout << start -> data << endl; //output
start = start-> next; //move to next node
}
}
// travel until your location’s next is NULL, end of list, and make that pointer to new node
void linkList :: append(int v)
{
if(head == NULL) //if head is not set
head = new node (v); //set head
else
{
node* start; //our traveling pointer
start = head; //start from the head
while(start->next != NULL) //while it’s next is not null
{
start = start -> next; //move to next
}
start->next = new node (v); //set next as new node
}
}
//travel until you find your target and have pointer before it to next of your target
void linkList :: erase(int v)
{
node *ptr, *pptr; //two traveling pointers
if(head != NULL) //if head is not null
{
if (head -> data == v) //if head’s data match our target
{
ptr = head; //set ptr to head
head = head -> next; //move head to next
delete ptr; //delete ptr
}
else
{
ptr = head; //ptr to head
while(ptr != NULL && ptr -> data != v) //move until match data OR end of list
{
pptr = ptr; //set pptr to ptr, so pptr is one before ptr
ptr = ptr -> next; //move ptr to next
}
if(ptr != NULL) //if we are not at end of list
{
pptr -> next = ptr -> next; //set pointer of a node before our deletion target’s next to our
// taget’s next, I know it’s confusing… sorry for my little english
delete ptr; //delete ptr
}
}
}
}
linkList :: ~linkList()
{
node *ptr, *pptr; //two pointers
ptr = head; //start from head
while(ptr != NULL) //while it’s not end of list
{
pptr = ptr-> next; //pptr is one after ptr
delete ptr; //delete ptr
ptr = pptr; //ptr is pptr;
}
}
/* insertNode function assumes you put data in order */
void linkList:: insertNode(int v)
{
node *ptr, *pptr;
if (haed == NULL || head -> data >= v) //if head is null or head’s data is bigger than given
{
head = new node(v, head); //make new head, and have its next pointer to old head
}
else
{
pptr = head;
ptr = head -> next;
while (ptr != NULL && ptr -> < v) //while we are not at the end of list and ptr is less than given
{
pptr = ptr;
ptr = ptr->next;
}
pptr -> next = new node(v, ptr); //create link between pptr and have our new node point to ptr
}
}
I hope comments are self explanatory…
And I don’t know if you noticed or not, link list doesn’t have set amount of capacity. It grows and shrinks as we add or delete data, and it’s really easy to insert middle of the list unlike array. In order to insert data in the middle of array you would have to copy current data to temporary block of memory and resize capacity and copy temp to resized array, assuming you have max capacity array. While link list all you have to do is make new node and change pointers…
That’s why people may argue that it’s more efficient, but pure straight line link list isn’t that efficient at all because there isn’t really good algorithms for search, sort or anything… It’s inevitable(1) to have, at worst case, big O (n) for search, and
...............n
big O ( (sigma) n^i) would be algorithm for sort…. I think…. //ignore dots, needed since forum deletes space or tab... it's used to express summation algorithm
.............i = 0
(1) I say it’s inevitable because we can’t use effective array algorithm due to lack of bracket operators…. Since we would have to go to node before our target to actually know the address of our target… which mean we would have to visit every node before our target to get to our target….
<!—END --!>
I feel this is the sloppiest work I’ve ever done… but I really can’t think of better way to show it to you then source code…
I hope you see the pros and cons of link list, and you may decided cons of linklist is far greater then pros....
But imagine the case of Queue..... It's way easier to do it with queue since with array you would have some blank memory blocks at the beginning that is little tricky to manage, although possible and very fun to write code for it...
And as I've mentioned earlier.... there is way to make alternation to link list so it would be able to use better and faster algorithm.... like in my book word frequency counter program... when you use enhanced version of link list it's so much much faster...
I may write article about it later.... but I think my summer jobs gonna be awesome and really time consuming....
Also C++ have linked list implemented and you can utilized it by key word list just like vectors.... but best way to understand how it works is by making one...
Posted by 
