Linked lists are one of those things you will never really understand if you just try to hack through someone else’s code.
The very first thing you need is a literal piece of paper and some kind of stylus. (Construction paper and crayons are most fun.)
Then draw pictures, with little boxes holding values and little arrows pointing to other boxes or to nothing (aka NULL aka
nullptr).
Then you need an arrow or two more to keep track of head, traversal, insertions, deletions, etc. Think it through step by step so that nothing gets lost.
Only
then are you ready to start writing code. Use the simplest data structure possible:
1 2 3 4 5
|
struct node
{
int value;
node* next;
};
|
And, if you want, an encapsulating type with some useful methods:
1 2 3 4 5 6 7 8 9 10 11 12
|
struct linked_list
{
node* head;
linked_list() : head{nullptr} { }
void append( int value );
void insert( int value, int index );
void remove( int index );
int size() const;
bool empty() const;
};
|
And, for testing, you want to be able to iterate through the list and print all the elements:
1 2 3 4
|
void print( const linked_list& xs )
{
...
}
|
Your
main() practically writes itself:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
|
int main()
{
linked_list xs;
std::cout << "size of list = " << xs.size() << "\n";
xs.append( 2 ); std::cout << "xs = "; print( xs );
xs.append( 5 ); std::cout << "xs = "; print( xs );
xs.append( 7 ); std::cout << "xs = "; print( xs );
xs.insert( 3, 1 ); std::cout << "xs = "; print( xs );
xs.remove( 0 ); std::cout << "xs = "; print( xs );
xs.remove( xs.size() - 1 ); std::cout << "xs = "; print( xs );
std::cout << "size of list = " << xs.size() << "\n";
// etc
}
|
Hope this helps.