C++

Forum

 
Please help me

abuh (20)
Consider the following implementation of the node and doubly linked-list:
Extend the class doubly_linked_list by adding the following methods:

1-Largest method .This method should return the largest element in a doubly linked-list.
2-Delete method. This method should delete the first occurrence of an element (value) from a doubly linked-list.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
 
#include<iostream>
using namespace std;
template <class type>
class node
{
public:
	type info;
	node<type> * next;// next
	node<type> * prev;//back

};

template <class type>
class doubly_linked_list
{
	//data members
private:
	node<type> *head, *tail;
	int length;
public:
	doubly_linked_list()
	{
		head = tail = NULL;
		length = 0;
	}
	bool isEmpty()
	{   // return (head==NULL);
		if (head == NULL)
			return true;
		else
			return false;
	}

	void Append(type e)
	{
		node<type> *newnode = new node<type>;
		newnode->info = e;
		if (isEmpty())
		{
			newnode->next = NULL;
			newnode->prev = NULL;
			head = newnode;
			tail = newnode;
		}
		else
		{
			tail->next = newnode;
			newnode->prev = tail;
			newnode->next = NULL;
			tail = newnode;
		}
		++length;

	}

	void Display()
	{
		if (isEmpty()) { cout << "The linked list is empty !!!!"; return; }
		cout << "list elements: ";
		node<type> * current = head;
		while (current != NULL)
		{
			cout << current->info << " ";
			current = current->next;
		}
		cout << endl;

	}

	void ReverseDisplay()
	{
		if (isEmpty()) { cout << "The linked list is empty !!!!"; return; }
		cout << "Reverse list elements: ";
		node<type> * current = tail;
		while (current != NULL)
		{
			cout<< current->info<<" ";
			current = current->prev;
		}
		cout << endl;
	}

	void insert(type e, int index)
	{
		if (index< 1 || index>length + 1)
		{
			cout << "Invalid index !!!!"; return;
		}
		else
		{
			node<type> * newnode = new node <type>;
			newnode->info = e;
			if (index == 1)
			{
				newnode->prev = NULL;
				if (isEmpty())
				{
					newnode->next = NULL;
					head = tail = newnode;
				}
				else {
					newnode->next = head;
					head->prev = newnode;
					head = newnode;
				}



			}
			else
			{
				node<type> * current = head;
				int i = 1;
				while (i != index - 1)
				{
					current = current->next;
					++i;
				}

				if(current !=tail)
				{ 
				current->next->prev = newnode;
				newnode->next = current->next;
				current->next = newnode;
				newnode->prev = current;
				}
				else
				{
					current->next = newnode;
					newnode->prev = current;
					newnode->next = NULL;
					tail = newnode;
				}

			}





		}
	}

};
Last edited on
Handy Andy (5051)
Hello abuh,

Have a look at http://www.cplusplus.com/forum/beginner/278188/ and see if that has anything that can help.

Andy
seeplus (6597)
You should have a chat with your colleague mick777! See http://www.cplusplus.com/forum/beginner/278188/

dhayden (5798)
Study the code that you're given to be sure you understand how it works. There is at least one bug.

Write some test code. Here is a version of the code with a test program. Running the test should help you find the bug(s). The underlined code is stuff that I added or changed.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
 
#include <iostream>
using std::cout;
using std::endl;

template < class type > class node {
public:
    type info;
    node < type > *next;			 // next
    node < type > *prev;			 //back

};

template < class type > class doubly_linked_list {
    //data members
private:
    node < type > *head, *tail;
    int length;
public:
    doubly_linked_list() {
	head = tail = nullptr;
	length = 0;
    }
    bool isEmpty()
    {						 // return (head==nullptr);
	if (head == nullptr)
	    return true;
	else
	    return false;
    }

    void Append(type e)
    {
	node < type > *newnode = new node < type >;
	newnode->info = e;
	if (isEmpty()) {
	    newnode->next = nullptr;
	    newnode->prev = nullptr;
	    head = newnode;
	    tail = newnode;
	} else {
	    tail->next = newnode;
	    newnode->prev = tail;
	    newnode->next = nullptr;
	    tail = newnode;
	}
	++length;

    }

    void Display()
    {
	if (isEmpty()) {
	    cout << "The linked list is empty !!!!";
	    return;
	}
	cout << length << " list elements: "; // dmh
	node < type > *current = head;
	while (current != nullptr) {
	    cout << current->info << " ";
	    current = current->next;
	}
	cout << endl;

    }

    void ReverseDisplay()
    {
	if (isEmpty()) {
	    cout << "The linked list is empty !!!!";
	    return;
	}
	cout << length << " Reverse list elements: "; // dmh
	node < type > *current = tail;
	while (current != nullptr) {
	    cout << current->info << " ";
	    current = current->prev;
	}
	cout << endl;
    }

    void insert(type e, int index)
    {
	if (index < 1 || index > length + 1) {
	    cout << "Invalid index !!!!";
	    return;
	} else {
	    node < type > *newnode = new node < type >;
	    newnode->info = e;
	    if (index == 1) {
		newnode->prev = nullptr;
		if (isEmpty()) {
		    newnode->next = nullptr;
		    head = tail = newnode;
		} else {
		    newnode->next = head;
		    head->prev = newnode;
		    head = newnode;
		}

	    } else {
		node < type > *current = head;
		int i = 1;
		while (i != index - 1) {
		    current = current->next;
		    ++i;
		}

		if (current != tail) {
		    current->next->prev = newnode;
		    newnode->next = current->next;
		    current->next = newnode;
		    newnode->prev = current;
		} else {
		    current->next = newnode;
		    newnode->prev = current;
		    newnode->next = nullptr;
		    tail = newnode;
		}

	    }

	}
    }
};

void
showit(doubly_linked_list<int> &ll)
{
    ll.Display();
    ll.ReverseDisplay();
}
 

int main()
{
    doubly_linked_list<int> ll;

    cout << "Append tests\n";
    showit(ll);
    ll.Append(12);
    showit(ll);
    ll.Append(18);
    showit(ll);
    ll.Append(3);
    ll.Append(200);
    showit(ll);

    cout << "insert tests\n";
    ll.insert(22, 0);
    ll.insert(22, 15);
    for (int i=1; i< 8; i += 2) {
	ll.insert(i*100, i);
	showit(ll);
    }
    
}



Once you understand how it works, write the largest() method. This is pretty easy since it just walks through the list and finds the largest item.

Delete is harder. Be sure to handle all of these issues:
- The element isn't in the list
- Deleting the first item
- Deleting the only item
- Deleting the last item
- Deleting from the middle of the list
- Don't forget to update the length.

When writing Delete, anytime you find yourself updating a next pointer, you probably need to update a prev pointer also (and vice versa). Anytime you update head, there's probably a case where you need to update tail, and vice versa.
abuh (20)
dhayden Your code is not required.Please see the question well
dhayden (5798)
abuh, I understand that my code isn't required. I thought it would help you understand the existing code, which will help you write the code you need. Also, I hope to encourage you to expand the test program to help you test your Delete() and Largest() methods.
Topic archived. No new replies allowed.