Linked List

This is a discussion on Linked List within the C++ Programming forums, part of the General Programming Boards category; I made a linked list program with some functions: Code: void newNode(); // add a node to the list int ...

  1. #1
    C / C++
    Join Date
    Jan 2006
    Location
    The Netherlands
    Posts
    312

    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;
    }
    Operating Systems:
    - Ubuntu 9.04
    - XP

    Compiler: gcc

  2. #2
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    >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.
    My best code is written with the delete key.

  3. #3
    (?<!re)tired Mario F.'s Avatar
    Join Date
    May 2006
    Location
    Portugal
    Posts
    7,456
    Unfortunately g++ allows for that uglyness
    The programmer’s wife tells him: “Run to the store and pick up a loaf of bread. If they have eggs, get a dozen.”
    The programmer comes home with 12 loaves of bread.


    Originally Posted by brewbuck:
    Reimplementing a large system in another language to get a 25% performance boost is nonsense. It would be cheaper to just get a computer which is 25% faster.

  4. #4
    C / C++
    Join Date
    Jan 2006
    Location
    The Netherlands
    Posts
    312
    I use a vector instead of the array now.
    Operating Systems:
    - Ubuntu 9.04
    - XP

    Compiler: gcc

  5. #5
    Registered User
    Join Date
    Jan 2005
    Posts
    7,317
    >> Unfortunately g++ allows for that uglyness
    C99 allows it, and the next C++ standard might as well.

  6. #6
    System Novice siavoshkc's Avatar
    Join Date
    Jan 2006
    Location
    Tehran
    Posts
    1,231
    I invite you to my thread:
    Link List

    Have you ever used <stack> header? I think it is a good practice to write a code that behaves exactly like that.
    Learn C++ (C++ Books, C Books, FAQ, Forum Search)
    Code painter latest version on sourceforge DOWNLOAD NOW!
    Download FSB Data Integrity Tester.
    Siavosh K C

  7. #7
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    >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.
    My best code is written with the delete key.

  8. #8
    System Novice siavoshkc's Avatar
    Join Date
    Jan 2006
    Location
    Tehran
    Posts
    1,231
    I am sorry, I meant nearly like that. It can only deals with ints.
    Learn C++ (C++ Books, C Books, FAQ, Forum Search)
    Code painter latest version on sourceforge DOWNLOAD NOW!
    Download FSB Data Integrity Tester.
    Siavosh K C

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. C++ Linked list program need help !!!
    By dcoll025 in forum C++ Programming
    Replies: 1
    Last Post: 04-20-2009, 10:03 AM
  2. Following CTools
    By EstateMatt in forum C Programming
    Replies: 5
    Last Post: 06-26-2008, 10:10 AM
  3. Reverse function for linked list
    By Brigs76 in forum C++ Programming
    Replies: 1
    Last Post: 10-25-2006, 10:01 AM
  4. Template Class for Linked List
    By pecymanski in forum C++ Programming
    Replies: 2
    Last Post: 12-04-2001, 08:07 PM
  5. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 10:21 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21