patterncppMinor
Linked list implemented as classes, not imperative code
Viewed 0 times
implementedimperativeclassescodelistlinkednot
Problem
As an update to previous code I've submitted:
Improvements this time are mainly having everything moved to a class, before I plough on and add more functionality (I've come back to C++ after a few years away and this is a revision exercise).
Improvements this time are mainly having everything moved to a class, before I plough on and add more functionality (I've come back to C++ after a few years away and this is a revision exercise).
#include
#include "LinkedList.h"
class LinkedList
{
public:
LinkedList(void);
~LinkedList(void);
void traverseList();
int length();
void push(int data);
private:
struct node{
int data;
node *pointee;
};
node *head;
node *last;
int count;
};
LinkedList::LinkedList(void)
{
head = new node();
last = new node();
head->data = 0;
head->pointee = last;
last->data = 0;
last->data = NULL;
count = 2;
}
LinkedList::~LinkedList(void)
{
}
/*
To be replaced with an iterator and an overloaded print operator for output
*/
void LinkedList::traverseList(){
for(node *iterator = LinkedList::head ; iterator ; iterator = iterator->pointee)
{
std::cout data data = data;
newNode->pointee = NULL;
last = newNode;
++count;
}
int main(){
LinkedList list;
for(int i=1 ; i<4 ; i++)
{
list.push(i);
}
int length = list.length();
std::cout << length << std::endl;
list.traverseList();
return 0;
}Solution
Since we have no clean implementations:
The thing to notice is that the push_back() and erase() become trivial if you use a sentinal. This is because you do not need to test for NULL in any part of the code.
Here is the whole code
Then Main
```
#include
#include
int main()
{
LinkedList list;
list.push_back(5);
LinkedList::iterator item = list.push_back(7);
for(LinkedList::iterator loop = list.begin(); loop != list.end(); ++loop)
{
std::co
The thing to notice is that the push_back() and erase() become trivial if you use a sentinal. This is because you do not need to test for NULL in any part of the code.
Node(Node* after)
{
prev = after;
next = after->next;
prev->next = this;
next->prev = this;
}
~Node()
{
prev->next = next;
next->prev = prev;
}
iterator push_back(T const& value)
{
tail = new ValueNode(value, tail);
// If new succeeded then increment count
++count;
return iterator(tail);
}
void erase(iterator const& i)
{
// Get the value we will set as tail if the delete works
Node* newTail = (tail == i.node)
? i.node->prev
: tail;
delete i.node;
// Delete worked now we can update the state.
tail = newTail;
--count;
}Here is the whole code
#ifndef THORS_ANVIL_UTILITY_LINKED_LIST
#define THORS_ANVIL_UTILITY_LINKED_LIST
#include
#include
template
class LinkedList
{
struct Node
{
Node* prev;
Node* next;
Node(Node* after)
{
prev = after;
next = after->next;
prev->next = this;
next->prev = this;
}
~Node()
{
prev->next = next;
next->prev = prev;
}
void swap(Node& rhs) throw() { std::swap(prev, rhs.prev); std::swap(next, rhs.next);}
};
struct ValueNode: Node
{
ValueNode(T const& value, Node* after)
: Node(after)
, data(value)
{}
T data;
};
Node head;
Node* tail;
int count;
public:
struct Iterator: std::iterator
{
Iterator(Node* node): node(node){}
T& operator*() {return static_cast(node)->data;}
T* operator->() {return &static_cast(node)->data;}
T const& operator*() const {return static_cast(node)->data;}
T const* operator->() const {return &static_cast(node)->data;}
Iterator& operator++() /*prefix*/ { node = node->next; return *this;}
Iterator& operator--() /*prefix*/ { node = node->prev; return *this;}
Iterator operator++(int) /*postfix*/ { Iterator result(*this);this->operator++(); return result;}
Iterator operator--(int) /*postfix*/ { Iterator result(*this);this->operator--(); return result;}
bool operator !=(Iterator const& rhs) const { return node != rhs.node;}
bool operator ==(Iterator const& rhs) const { return !(*this != node);}
mutable Node* node;
};
LinkedList()
: tail(&head)
, count(0)
{}
~LinkedList()
{
clear();
}
void clear()
{
while(head.next != &head)
{
Node* old = head.next;
head.next = head.next->next;
--count;
delete old;
}
}
LinkedList(LinkedList const& copy)
: tail(&head)
, count(0)
{
std::for_each(copy.head->next, copy.head, std::bind1st(std::mem_fun(&LinkedList::push_back), this));
}
LinkedList& operator=(LinkedList rhs)
{
rhs.swap(*this);
return *this;
}
void swap(LinkedList& rhs) throw()
{
std::swap(head, rhs.head);
std::swap(tail, rhs.tail);
std::swap(count, rhs.count);
}
bool isEmpty() const { return &head == tail; }
size_t size() const { return count; }
typedef Iterator iterator;
typedef Iterator const const_iterator;
iterator push_back(T const& value)
{
tail = new ValueNode(value, tail);
++count;
return iterator(tail);
}
void erase(iterator const& i)
{
Node* newTail = (tail == i.node)
? i.node->prev
: tail;
tail = newTail;
--count;
delete i.node;
}
iterator begin() {return iterator(head.next);}
const_iterator begin() const {return iterator(head.next);}
iterator end() {return iterator(&head);}
const_iterator end() const {return iterator(&head);}
};
#endifThen Main
```
#include
#include
int main()
{
LinkedList list;
list.push_back(5);
LinkedList::iterator item = list.push_back(7);
for(LinkedList::iterator loop = list.begin(); loop != list.end(); ++loop)
{
std::co
Code Snippets
Node(Node* after)
{
prev = after;
next = after->next;
prev->next = this;
next->prev = this;
}
~Node()
{
prev->next = next;
next->prev = prev;
}
iterator push_back(T const& value)
{
tail = new ValueNode(value, tail);
// If new succeeded then increment count
++count;
return iterator(tail);
}
void erase(iterator const& i)
{
// Get the value we will set as tail if the delete works
Node* newTail = (tail == i.node)
? i.node->prev
: tail;
delete i.node;
// Delete worked now we can update the state.
tail = newTail;
--count;
}#ifndef THORS_ANVIL_UTILITY_LINKED_LIST
#define THORS_ANVIL_UTILITY_LINKED_LIST
#include <algorithm>
#include <functional>
template<typename T>
class LinkedList
{
struct Node
{
Node* prev;
Node* next;
Node(Node* after)
{
prev = after;
next = after->next;
prev->next = this;
next->prev = this;
}
~Node()
{
prev->next = next;
next->prev = prev;
}
void swap(Node& rhs) throw() { std::swap(prev, rhs.prev); std::swap(next, rhs.next);}
};
struct ValueNode: Node
{
ValueNode(T const& value, Node* after)
: Node(after)
, data(value)
{}
T data;
};
Node head;
Node* tail;
int count;
public:
struct Iterator: std::iterator<std::input_iterator_tag, T, ptrdiff_t, const T*, const T&>
{
Iterator(Node* node): node(node){}
T& operator*() {return static_cast<ValueNode*>(node)->data;}
T* operator->() {return &static_cast<ValueNode*>(node)->data;}
T const& operator*() const {return static_cast<ValueNode*>(node)->data;}
T const* operator->() const {return &static_cast<ValueNode*>(node)->data;}
Iterator& operator++() /*prefix*/ { node = node->next; return *this;}
Iterator& operator--() /*prefix*/ { node = node->prev; return *this;}
Iterator operator++(int) /*postfix*/ { Iterator result(*this);this->operator++(); return result;}
Iterator operator--(int) /*postfix*/ { Iterator result(*this);this->operator--(); return result;}
bool operator !=(Iterator const& rhs) const { return node != rhs.node;}
bool operator ==(Iterator const& rhs) const { return !(*this != node);}
mutable Node* node;
};
LinkedList()
: tail(&head)
, count(0)
{}
~LinkedList()
{
clear();
}
void clear()
{
while(head.next != &head)
{
Node* old = head.next;
head.next = head.next->next;
--count;
delete old;
}
}
LinkedList(LinkedList const& copy)
: tail(&head)
, count(0)
{
std::for_each(copy.head->next, copy.head, std::bind1st(std::mem_fun(&LinkedList::push_back), this));
}
LinkedList& operator=(LinkedList rhs)
{
rhs.swap(*this);
return *this;
}
void swap(LinkedList& rhs) throw()
{
std::swap(head, rhs.head);
std::swap(tail, rhs.tail);
std::swap(count, rhs.count);
}
bool isEmpty() const { return &head == tail; }
size_t #include <LinkedList.h>
#include <iostream>
int main()
{
LinkedList<int> list;
list.push_back(5);
LinkedList<int>::iterator item = list.push_back(7);
for(LinkedList<int>::iterator loop = list.begin(); loop != list.end(); ++loop)
{
std::cout << *loop << "\n";
}
list.erase(item);
for(LinkedList<int>::iterator loop = list.begin(); loop != list.end(); ++loop)
{
std::cout << *loop << "\n";
}
}after
######### #########
--># Next #------------------------># Next #----
# # # #
---#Prev #<------------------------#Prev #<---
######### #########
NewNode(this)
#########
# Next#
#Prev #
#########after
######### #########
--># Next #------------------------># Next #----
# # # #
---#Prev #<------------------------#Prev #<---
######### | #########
|
| (this)
| #########
| # Next#
-----#Prev #
#########Context
StackExchange Code Review Q#9230, answer score: 7
Revisions (0)
No revisions yet.