need help with first attempt at linked list

This is a discussion on need help with first attempt at linked list within the C++ Programming forums, part of the General Programming Boards category; hi everyone! i am writing a symbol table, and originally had it working as a std::vector<Token> (Token is my class ...

  1. #1
    Registered User
    Join Date
    Sep 2013
    Posts
    10

    need help with first attempt at linked list

    hi everyone! i am writing a symbol table, and originally had it working as a std::vector<Token> (Token is my class to hold an entry in the symbol table) I realized that i was just going to be continuosly iterating over it and not actually ever looking up, so i decided to write in a linked list, for more efficiency, and because it was time to learn how to write one. however when i went to write it I got segment fault(core dumped) but i dont know where the memory issue is

    here it Token.cpp:
    Code:
    #include <iostream>
    #include <string>
    
    #include "Token.hpp"
    
    using namespace std;
    using std::string;
    
    Token::Token() {}
    Token::Token(string type, string name, long line, long column)
        : Type(type), Name(name), Line(line), Column(column) {}
    
    void Token::SetType   (string type) { this->Type   = type;   }
    void Token::SetName   (string name) { this->Name   = name;   }
    void Token::SetLine   (long line)   { this->Line   = line;   }
    void Token::SetColumn (long column) { this->Column = column; }
    
    string Token::GetType   () { return this->Type;   }
    string Token::GetName   () { return this->Name;   }
    long   Token::GetLine   () { return this->Line;   }
    long   Token::GetColumn () { return this->Column; }
    
    Token* Token::Begin() { return this->Start;                        }
    void   Token::Next () { *this = *this->Next_; this->Finish = this; }
    Token* Token::End  () { return Finish;                             }
    
    int main(int argc, char *argv[])
    {
        Token *TokenList = new Token;
    
        for(int Counter = 0; Counter < 10; Counter++)
        {
            TokenList = new Token("test", "test", Counter, Counter);
            TokenList->Next();
        }
    
        for(Token::Iterator Counter = TokenList->Begin(); Counter != TokenList->End(); Counter++)
            cout<< "no";
    }
    (when i get it write im taking out the using namespace std, iostream header, and main function but i need it right now for testing)

    Token.hpp
    Code:
    #ifndef _Token_hpp
    #define _Token_hpp
    
    #include <string>
    
    using std::string;
    
    class Token
    {
        string Type, Name;
        long Line, Column;
        Token *Start = this, *Next_, *Finish;
    
        public:
            Token();
            Token(string, string, long, long);
    
            void SetType   (string);
            void SetName   (string);
            void SetLine   (long);
            void SetColumn (long);
    
            string GetType   ();
            string GetName   ();
            long   GetLine   ();
            long   GetColumn ();
    
            Token* Begin();
            void   Next ();
            Token* End  ();
    
            typedef Token* Iterator;
    };
    #endif

  2. #2
    Registered User
    Join Date
    Apr 2013
    Posts
    1,262
    Normally for a linked list, there are two classes, one for the list, and one for the nodes. Each list structure has one or two pointers to nodes (the first and/or last node), and each node has one or two pointers to nodes (next and/or previous). The current code is combining these two classes into one class, which is probably the cause of the problem.

  3. #3
    Registered User hk_mp5kpdw's Avatar
    Join Date
    Jan 2002
    Location
    Northern Virginia/Washington DC Metropolitan Area
    Posts
    3,794
    Member functions that do not modify the object they refer to should be declared const, in this case all your "get" member functions would be candidates for this.





    Passing std::string objects into functions should usually be done via const reference unless you plan on having the function you are calling manipulate the passed in argument.





    This is concerning:
    Code:
    void   Token::Next () { *this = *this->Next_; this->Finish = this; }
    
    ...
    
    Token *TokenList = new Token;
     
    for(int Counter = 0; Counter < 10; Counter++)
    {
        TokenList = new Token("test", "test", Counter, Counter);
        TokenList->Next();
    }
    You have a memory leak where you constantly throw away your previous allocated memory each time through the loop. Resetting *this inside your Next function is scary. Also, calling the Next function when you never seem to initialize the Next_ pointer seems troublesome. Plenty of opportunities for segfaults in there.
    "Owners of dogs will have noticed that, if you provide them with food and water and shelter and affection, they will think you are god. Whereas owners of cats are compelled to realize that, if you provide them with food and water and shelter and affection, they draw the conclusion that they are gods."
    -Christopher Hitchens

  4. #4
    Registered User
    Join Date
    Apr 2013
    Posts
    1,262
    Quote Originally Posted by rcgldr View Post
    Normally for a linked list, there are two classes, one for the list, and one for the nodes. Each list structure has one or two pointers to nodes (the first and/or last node), and each node has one or two pointers to nodes (next and/or previous). The current code is combining these two classes into one class, which is probably the cause of the problem.
    Example:

    Code:
    class Token
    {
        string Type, Name;
        long Line, Column;
        Token *Next;
        public:
            Token();
            Token(string, string, long, long);
            void SetType   (string);
            void SetName   (string);
            void SetLine   (long);
            void SetColumn (long);
            string GetType   ();
            string GetName   ();
            long   GetLine   ();
            long   GetColumn ();
            Token* GetNext (){return this->Next;}
    };
    
    
    class TokenList
    {
        Token *Start, *Finish;
        public:
            TokenList(){Start = NULL; Finish = NULL;}
            Token* Begin(){return this->Start;}
            Token* Last (){return this->Finish;}
            PushBack();
            PopFront();
    }
    Last edited by rcgldr; 11-08-2013 at 12:14 PM.

  5. #5
    Registered User
    Join Date
    Sep 2013
    Posts
    10
    sorry about the late reply. thanks for all of the help! so how would i implement PushBack and PopFront?

  6. #6
    Registered User
    Join Date
    Apr 2013
    Posts
    1,262
    Quote Originally Posted by DTSCode View Post
    sorry about the late reply. thanks for all of the help! so how would I implement PushBack and PopFront?
    PushBack() appends a node to the end of a list. PopFront() removes a node from the beginning of a list and returns a pointer to the removed node (or it returns NULL if the list is empty).

  7. #7
    Registered User
    Join Date
    Sep 2013
    Posts
    10
    thanks everyone for the help!

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 13
    Last Post: 09-22-2013, 10:34 PM
  2. C Linked List - first attempt.
    By (^Burt^) in forum C Programming
    Replies: 18
    Last Post: 09-18-2013, 01:46 PM
  3. Linked lists; My first attempt
    By relyt_123 in forum C++ Programming
    Replies: 9
    Last Post: 11-05-2007, 01:54 PM
  4. Problem with my first linked list attempt.
    By SlyMaelstrom in forum C++ Programming
    Replies: 3
    Last Post: 11-09-2005, 03:33 AM
  5. Replies: 6
    Last Post: 03-02-2005, 01:45 AM

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