link list doubly type,me confuse,help?

[squanto]

hello,
Well, its almost the end of the semester and everyone is anxious to take a vacation. But not me I wish we had more time so that I can use that time to better understand the topic, "Linked List". yes, thats what I need help with.
I am either very confuse or just plain stupid. Well lets not go there. Anyway,I know there are three types of linked list. Singly,doubly,and a tree. Doubly is what I need help with.

Questions:

-Linked list principal and how it works?
-whats a head?And what is its role?
-Whats a pointer link? And whats its role?
-Is a linked list similar to an array?
-How do I insert, delete, locate, and print out the values?Please give example.

Thankyou all in advance for your uncommon efforts in helping me to understand this topic. And happy holiday!

 

[programsecrets]

-whats a head?And what is its role?
The HEAD serves as the entry point for the linked list. It's value is a pointer to the physical memory location (address) of the first node in the linked list. A node contains the data the user is interested in as well as a pointer link to the next node (and, if it's a double linked list, it also contains a pointer link to the previous node).

-Whats a pointer link? And whats its role?
It's a data element in each node which points to the physical memory location of the node which follows in the list.

-Linked list principal and how it works?
A linked list is like a group of web pages. Each page contains data, but only one hyperlink (pointer link) to get to the next web page. So, in order to get to the fifth web page, you must go to page one, click on the hyperlink, which takes you to page two, click on the hyperlink, and so on, until you recognize that you are at the page you want, the fifth one.

Now imagine that the only web page address you ever learn is the first web page. Imagine you do not have a "back" button to get to the previous page, or a history list. This would mean that every time you wanted to find a web page, you would have to start at the first page, the HEAD, which serves as the entry point for the set of web pages (or linked list). You would then traverse through each page in a linear manner (you can't jump past pages), until you found the one you were looking for.

- you also wanted to know about double linked lists
They are like a web page that has a hyperlink to the previous page as well as the next page so that you can navigate in either direction, but in a linear way.

In the linked list, each node physically contains a data pointer to the previous node, a data pointer to the next node, as well as the actual data the user is interested in. In the head node, the pointer to the previous node would be NULL. In the tail node, the pointer to the next node would be NULL. That's how you would know as you were traversing the list if you had arrived at the end or at the beginning of the list.

A person designing the flow of the web pages pages could add another one at any time, simply by modifying the hyperlink on the last page to point to the new page. If they wanted to delete a page, they would modify the link on the previous page to skip the current page and point to the next page. Then, the current page could be removed. An inserted page would be handled in a similar way.

One advantage of linked lists is that linked elements can be added or removed dynamically, to allow the total number of elements in the linked list continue to grow or shrink as needed.

-Is a linked list similar to an array?
Let's illustrate an array using the web page example. Imagine you are using a frame (or boxed area on the left side of the web page) that contained an index of links which allowed you to go directly to any page that you wanted. This index would save you from having to traverse each and every page until you found the one you wanted. However, imagine that you were unable to add more indexes. You have to know in advance the maximum number of pages, so you could initially set up the index directory properly.

Historically, the main disadvantage of arrays was that you could not change the total number of elements dynamically. You had to allocate a specific number (i.e. int MyData[50] -- which allocates 50 elements... what if later, you decided that you really needed 75 as the program was running?)

-How do I insert, delete, locate, and print out the values?
I'm going to take a breather. X-) Please read what I've written so far. If and when I get enough time, I may take a crack at giving you an example, unless someone else beats me to it.

Hope the web page example helps. Let me know if something is still unclear.

 

[Guest_imported]

hi programsecret,
Your tutorial was very helpful and I thankyou very much.
But I still want to know about
How do I insert, delete, locate, and print out the values?
When ever you have time, no rush.Again thankx.

 

[programsecrets]

How about if you give us a small sample of how you think you would start the exersize and then we can guide you. That will help you learn better. If you don't know the exact syntax, then show a mix of c and pseudocode or comments. I'll be willing to help you if you show you're willing to work too.

 

[Guest_imported]

hello again,
here is the part that I just couldnt figure out how to do.The Append function for the class implementation function.If you look at the main program
main is giving the Append function some arguments to be inserted into the linked list. The problem I am having is
creating the the head,ect.. and linked them up. Also I dont know where the forward link and backward link go either.



#include <iostream>
using namespace std;

struct NodeType //double link node
{
int component;
NodeType* forwardlink;
NodeType* backlink;
};

class ClosedList {
public:
void Append(int item );
ClosedList(){head==NULL;}
private:
NodeType* head;
};

void ClosedList::Append(int item )
{
////////Hmmmmmm?
NodeType *NewItem,*CurrPTR;

head= new NodeType;
head->component=item;

NewItem= new NodeType;
NewItem->component=item;
/////////????
//how about the forward Link and backward link?




}


void main()
{
ClosedList Scores;
Scores.Append(92);
Scores.Append(82);
Scores.Append(62);
Scores.Append(72);
Scores.Append(99);
}

 

[programsecrets]

Since I don't want to just give you the answers, here are some questions to make you think:

Which item in the linked list is the head pointing to:
1) when the program starts?
answer: there are no items in the list
2) after your first call to the Append function?
answer: should be 1st item
3) after your second call to the Append function?
answer: should still be 1st item... but is it?

Given what you know about linked lists, should the head pointer change each time? Once it is allocated, the head should always point to the first entry in the list. As new things are appended to the list, they should not replace the head pointer. How do you attach new items to the end of the list? Clue: use the &quot;next&quot; item pointer instead of the head pointer. But think it through carefully, so that you're always appending to the end of the list.

Also think about how you can keep track of the CURRENT node so that each time you add an item, you don't have to navigate the entire list before adding it...

Okay? See what you can do to change these things.