patterncppModerate
C++ Linked List Implementation
Viewed 0 times
listimplementationlinked
Problem
I'm learning C++ and also about data structures, so I am trying to implement some. This is my linked list. I've included two different ways of getting the length of the list, with a
length variable and also a function (getLength2) that goes through the list until it finds a NULL pointer. I suspect that there could be memory leaks in it, though I'm not sure.#include "stdafx.h"
#include
using namespace std;
template
class linked_list{
struct node{
val value;
node *next;
};
node *start;
unsigned int length;
public:
linked_list() { length = 0; start = NULL; }
unsigned int getLength() { return length; }
val getFirst() { return (*start).value; }
unsigned int getLength2();
void add(val value);
val getVal(unsigned int pos);
val pop();
};
int _tmain(int argc, _TCHAR* argv[])
{
linked_list gary;
for (int i = 0; i 0; ++k){
cout
void linked_list::add(val value){
node *second = start;
start = new node;
(*start).value = value;
(*start).next = second;
length += 1;
}
template
val linked_list::getVal(unsigned int pos){
node current = *start;
for (unsigned int depth = 0; depth
val linked_list::pop(){
val ret = start->value;
node *new_address = start->next;
delete start;
start = new_address;
length -= 1;
return ret;
}
template
unsigned int linked_list::getLength2() {
if (start == NULL){
return 0;
}
node current = *start;
unsigned int len = 1;
while (current.next != NULL){
current = *(current.next);
len += 1;
}
// should this have a 'delete current'?
return len;
}Solution
-
Your "getters" should be
-
The constructor can instead be an initializer list:
-
Be aware of the issues regarding
-
If you have a C++11-compliant compiler, use
-
Be aware that
-
Since you're using
Your "getters" should be
const since they don't modify any data members. This will also protect you against any accidental modifications in those functions.unsigned int getLength() const { return length; }-
The constructor can instead be an initializer list:
linked_list() : length(0), start(NULL) {}-
Be aware of the issues regarding
using namespace std.-
If you have a C++11-compliant compiler, use
nullptr instead of NULL.-
Be aware that
_tmain() and _TCHAR are non-portable, so anyone using this code outside of Visual Studio will not be able to compile it. In order to make this portable, change them to main() and char respectively.-
Since you're using
std::pow(), you should include `. Although is already covering it, you should add this library anyway.
-
There's not really a need for getLength2(). You just need to increment or decrement length, depending on the list operation. Your inline "getter" will, of course, return this updated length.
Regarding incrementing/decrementing, length += 1 and length -= 1 can respectively be length++ and length--.
-
The val argument for add() should be passed by const&, especially if it happens to be of a non-primitive type.
-
You should consider error-checking (empty list) in pop() if you'd still like it to return the popped value. Otherwise, you can make it void and simply return if the list is already empty.
-
Instead of (*start).value, use the -> operator for readability: start->value`.Code Snippets
unsigned int getLength() const { return length; }linked_list() : length(0), start(NULL) {}Context
StackExchange Code Review Q#82770, answer score: 10
Revisions (0)
No revisions yet.