# C++ Question



## hikkifan84 (Feb 26, 2005)

I have to write a program using doubly linked lists. Apparently, my teacher thought it would be a good idea to give us an assignment on something she never taught us. She's never even mentioned Doubly-linked lists in class. Her exact words were "Read the section in your textbook." Well, I read it and it's not helping me, at all. We have done linked lists in the class and we're supposed to use the linked list program to write the doubly linked list. I think she wants us to modify it. I have 10 functions to write. Can anyone help me? I really just need someone to show me an example of how to go from a single linked list to a doubly linked list and I'm sure I could figure out the rest from there. I have this much done:



> typedef NodeType* NodePtr;
> 
> struct NodeType {
> ItemType data;
> ...



One of the functions I have to write in the insert function. Here is my Insert function for a single linked list:


> void SortedList::Insert(ItemType item) {
> NodePtr current; // Moving pointer
> NodePtr prev; // Pointer to node before *current
> NodePtr newNode; // Pointer to new node
> ...


How would I modify that for a doubly linked list?


----------



## mgoldb2 (Dec 16, 2004)

few question about how your teacher define a double link list. I am gussing it mean each node has a backward and forward pointer. Is this correct? If so does it need to be circular or just linear meaning does the first node back pointer point to NULL and the last node foward pointer points to NULL. or is it circular meaning last pointer points to first pointer and first pointer points to last pointer. 

other questions what type of data we dealing with ints or chars or strings. Do the list need to be sorted or does the insert always go to the back.


----------



## mgoldb2 (Dec 16, 2004)

If I take the asumption it need to be sorted and it a forward and back link and it is not circular then I would edit the insert in the following way.

I will bold the changes I made



> void SortedList::Insert(ItemType item) {
> NodePtr current; // Moving pointer
> NodePtr prev; // Pointer to node before *current
> NodePtr newNode; // Pointer to new node
> ...


As you see there not many major changes for this particular problem. These changes depends on changing the struct of a linklist to have a forward and backward pointer on each node. It also depends on prober making of the constructor.

Some more changes would need to be made if you needed to keep track of the end pointer instead of only the head pointer.


----------



## hikkifan84 (Feb 26, 2005)

Thank you so much! This definately helps me a lot. The list is already sorted and the first and last pointers have no predecessors.


----------



## mgoldb2 (Dec 16, 2004)

hikkifan84 said:


> Thank you so much! This definately helps me a lot. The list is already sorted and the first and last pointers have no predecessors.


Glad It helps but after looking over it I forgot to link the next node bakward to the previous the new code looks like this



> void SortedList::Insert(ItemType item) {
> NodePtr current; // Moving pointer
> NodePtr prev; // Pointer to node before *current
> NodePtr newNode; // Pointer to new node
> ...


I only added one new line which I bolded but it a important one.


----------

