Help with push_back and pop_back function in linked list class

Apr 17, 2016 at 4:31pm
I am doing a project for school that involves implementing a linked list class. I believe I have all of my functions correct except for my push_back and pop_back. My push_back needs to take a Node* as a parameter and add the node pointed to by the pointer to the end of the list. My pop_back function needs to remove the last node from the list, and return a pointer to this node. Do not delete the node in this function. Simply unlink it from the list. Any help would be great. Here is my class:


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
Node::Node()
{
	next = NULL;
	book = NULL;
}

Node::Node(Book* _book)
{
	book = _book;
}


Node* Node::getNextNode() const
{
	return next;
}

void Node::setNextNode(Node* setter)
{
	next = setter;
}


Node::~Node()
{

}

Book* Node::getBook() const
{
	return book;
}




List::List()
{
	first = NULL;
	last = NULL;
	numNodes = 0;
}

//OK
List::~List()
{
	Node* current = first;
	while (current != NULL)
	{
		Node* deleter = current;
		current = current->getNextNode();
		delete deleter;
	}

}

void List::push_back(Node* item)
{
	if (last == NULL)
	{
		last = item;
		numNodes++;
	}
	else if (last != NULL)
	{
		item->setNextNode(last);
		last = item;
		numNodes++;
	}
}

// OK
void List::push_front(Node* item)
{
	if (first == NULL)
	{
		first = item;
		numNodes++;
	}
	else if(first != NULL)
	{
		item->setNextNode(first);
		first = item;
		numNodes++;
	}
}

Node* List::pop_back()
{
	Node* temp = first;
	temp = first;
	while (temp->getNextNode() != NULL)
	{
		temp = temp->getNextNode();

	}
	return temp;
	
}

// OK
Node* List::pop_front()
{

	Node* tempPtr = first;

	if (first == NULL)
	{
		return NULL;
	}

	else if (first != NULL)
	{
		first = first->getNextNode();
		numNodes--;
	}

	return tempPtr;
	
}

Node* List::getFirst() const
{
	return first;
}

Node* List::getLast() const
{
	return last;
}
Last edited on Apr 17, 2016 at 4:31pm
Apr 18, 2016 at 12:41am
closed account (D80DSL3A)
I'll help with your push_front() and pop_front() functions so the push_back and pop_back functions will work once they're written. The front functions are missing a detail.
Your push_front function need to assign last a value when the 1st Node is pushed onto an empty list.
That one Node is both 1st and last in the list:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// OK - almost
void List::push_front(Node* item)
{
	if (first == NULL)
	{
		first = item;
                last = first;// Assign last when 1st node pushed
		numNodes++;// should = 1. ++ should work though
	}
	else if(first != NULL)
	{
		item->setNextNode(first);
		first = item;
		numNodes++;
	}
}

When you pop the last Node, last must not be left pointing to it:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
Node* List::pop_front()
{

	Node* tempPtr = first;

	if (first == NULL)
	{
		return NULL;
	}

	else if (first != NULL)
	{
		first = first->getNextNode();// this line makes first = NULL if the last Node was popped.
		numNodes--;
                if( first == NULL ) last = NULL;// handle case of last Node popped.
	}

	return tempPtr;
	
}

Your back functions, even properly coded, would not have worked.
Similar considerations apply to push_back (if 1st node pushed this way then first = last must be assigned) and pop_back where first = NULL must be assigned when the last Node is popped off the back. Hope that gives you something to work on.
Last edited on Apr 18, 2016 at 12:48am
Apr 18, 2016 at 9:59pm
I cannot figure out the pop_back code. Any more tips?
Apr 18, 2016 at 10:19pm
For pop_back you have to first find the second to last node.
Apr 18, 2016 at 10:48pm
I know that, I just can't figure the code out to do it.
Apr 19, 2016 at 9:28am
The second to last node is the node that has the last node of the list as "next".

Your first attempt has a loop that repeats until you reach a node that has null as "next". That is the last node.

You have to modify your loop's condition so that it stops one node earlier. Your List has apparently two pointer members. Could one of those help?
Topic archived. No new replies allowed.