Thread: Linked List

I made a linked list program with some functions:

Code:

void newNode(); // add a node to the list
int readNode(int n); // read a specific node
void displayAll(); // display all node values
void reverseList(); // reverse the entire list
int countNodes(); // count the number of nodes in the list

I made this because I wanted to understand the point of a linked list. Can you tell me what I should change?

Code:

#include <iostream>

using namespace std;

class linklist
{
public:
struct node
{
	int num;
	node *next;
}*root,*walk;
	// methods
	linklist();
	~linklist();

	void newNode(); // add a node to the list
	int readNode(int n); // read a specific node
	void displayAll(); // display all node values
	void reverseList(); // reverse the entire list
	int countNodes(); // count the number of nodes in the list
};

linklist::linklist()
{
	root = new node;
	root->num = 1;
	root->next = NULL;
}

linklist::~linklist()
{
	delete root;
	delete walk;
}

void linklist::newNode()
{
	int x = root->num;
	walk = root;

	while(walk->next != NULL)
	{
		walk = walk->next;
		x++;
	}
	x++;
	walk->next = new node;
	walk = walk->next;
	walk->next = NULL;
	walk->num = x;
	cout << " " << walk->num;
}

int linklist::readNode(int n)
{
	if(n == 1)
	{
		return root->num;
	}

	walk = root;
	int i = 0;

	while(walk->next != NULL && i < n)
	{
		walk = walk->next;
		i++;
	}
	return walk->num;
}

void linklist::displayAll()
{
	walk = root;
	while(walk->next != NULL)
	{
		cout << " " << walk->num;
		walk = walk->next;
	}
	cout << " " << walk->num;
}

int linklist::countNodes()
{
	int x = root->num;
	walk = root;
	while(walk->next != NULL)
	{
		walk = walk->next;
		x++;
	}
	return x;
}

void linklist::reverseList()
{
	// variables
	const int numNodes = countNodes();
	int array[numNodes+1];
	int i = numNodes, x;

	walk = root;

	while(walk->next != NULL)
	{
		i--;
		array[i] = walk->num;
		walk = walk->next;
	}
	i--;
	array[i] = walk->num;

	for(i = 0; i < numNodes; i++)
	{
		cout << array[i];
	}

	root->next = NULL;
	root->num = array[0];
	walk->next = NULL;
	walk->num = 1;

	cout << "\nRoot: " << root->num;

	// insert the last node value into the first node value
	for(i = 0; i < (numNodes-1); i++)
	{
		while(walk->next != 0)
		{
			walk = walk->next;
		}
		walk->next = new node;
		walk = walk->next;
		walk->next = NULL;
		walk->num = array[i+1];
		cout << "\nNode " << i+1 << ": " << walk->num;
	}
}

int main()
{
	// variables
	linklist ll;
	int nodes;
	int numNodes;
	int n;
	int nodeVal;


	// execute functions
	cout << "Linked list\n";

	cout << "How many nodes: ";

	while(!(cin >> nodes))
	{
		cin.clear();
		cin.ignore(1000, '\n');
		cout << "Enter integer value: ";
	}

	cout << "Node values: " << ll.root->num;

	for(int i = 0; i < nodes; i++)
		ll.newNode();

	cout << "\nWhich node do you want to read? "; 
	while(!(cin >> n))
	{
		cin.clear();
		cin.ignore(1000, '\n');
		cout << "Enter integer value: ";
	}
	nodeVal = ll.readNode(n);
	cout << "Value of node nr. " << n << ": " << nodeVal << endl;

	cout << "Display all:";
	ll.displayAll();

	numNodes = ll.countNodes();
	cout << "\nNumber of nodes in the list: " << numNodes;

	cout << endl;

	ll.reverseList();

	cin.ignore(1000, '\n');
	cin.get();
	return 0;
}

>Can you tell me what I should change?

Code:

const int numNodes = countNodes();
int array[numNodes+1];

I'm surprised that this works. Most likely you're relying on a compiler extension. Just because numNodes is const doesn't mean you can use it as the size of an array if the initializer doesn't have the correct properties. In this case it relies on the run-time effect of walking over a linked list.

Unfortunately g++ allows for that uglyness

I use a vector instead of the array now.

I invite you to my thread:
http://cboard.cprogramming.com/showthread.php?t=81265

Have you ever used <stack> header? I think it is a good practice to write a code that behaves exactly like that.

>I think it is a good practice to write a code that behaves exactly like that.
That's hardly a challenge:

Code:

namespace std {
  template <typename T, typename C = deque<T> >
  class stack {
    template <typename U, typename C1>
    friend bool operator== ( const stack<U, C1>&, const stack<U, C1>& );

    template <typename U, typename C1>
    friend bool operator< ( const stack<U, C1>&, const stack<U, C1>& );
  public:
    typedef C                           container_type;
    typedef typename C::value_type      value_type;
    typedef typename C::size_type       size_type;
    typedef typename C::reference       reference;
    typedef typename C::const_reference const_reference;
  public:
    explicit        stack ( const C& init = C() ): c ( init ){}
    bool            empty() const { return c.empty(); }
    size_type       size() const { return c.size(); }
    reference       top() { return c.back(); }
    const_reference top() const { return c.back(); }
    void            push ( const value_type& x ) { c.push_back ( x ); }
    void            pop() { c.pop_back(); }
  protected:
    C c;
  };

  template <typename T, typename C>
  inline bool operator== ( const stack<T, C>& lhs, const stack<T, C>& rhs )
  {
    return lhs.c == rhs.c;
  }

  template <typename T, typename C>
  inline bool operator< ( const stack<T, C>& lhs, const stack<T, C>& rhs )
  {
    return lhs.c < rhs.c;
  }

  template <typename T, typename C>
  inline bool operator!= ( const stack<T, C>& lhs, const stack<T, C>& rhs )
  {
    return !(lhs == rhs);
  }

  template <typename T, typename C>
  inline bool operator> ( const stack<T, C>& lhs, const stack<T, C>& rhs )
  {
    return rhs < lhs;
  }

  template <typename T, typename C>
  inline bool operator<= ( const stack<T, C>& lhs, const stack<T, C>& rhs )
  {
    return !(rhs < lhs);
  }

  template <typename T, typename C>
  inline bool operator>= ( const stack<T, C>& lhs, const stack<T, C>& rhs )
  {
    return !(lhs < rhs);
  }
}

Now a standard deque, that's harder.

I am sorry, I meant nearly like that. It can only deals with ints.