CODEWITHSUNDEEP
c++algorithmdata-structureslinked-list
Ali
Ali

Reputation: 5476

C++: Linked List Representation

The way I know how to represent a linked list is basically creating a Node class (more preferably a struct), and the creating the actual linkedList class. However, yesterday I was searching for the logic of reversing a singly linked list operation and almost 90% of the solutions I've encountered was including that the function, returning data type Node* . Thus I got confused since if you want to reverse a list no matter what operation you done, wouldn't it be in the type of linkedList again? Am I doing it the wrong way?

The linked list implementation I do all the time;

#include <iostream>
using namespace std;

struct Node
{
    int data;
    Node *next;
};

class linkedList
{
public:
    Node* firstPtr;
    Node* lastPtr;

    linkedList()
    {
        firstPtr=lastPtr=NULL;
    }
    void insert(int value)
    {
        Node* newNode=new Node;
        newNode->data=value;
        if(firstPtr==NULL)
            firstPtr=lastPtr=newNode;
        else {
            newNode->next=firstPtr;
            firstPtr=newNode;
        }
    }
    void print()
    {
        Node *temp=firstPtr;
        while(temp!=NULL)
        {
            cout<<temp->data<<" ";
            temp=temp->next;
        }
    }
};

Upvotes: 1

Views: 2632

Answers (3)

Nilesh Barai
Nilesh Barai

Reputation: 1167

Those functions might be returning of type Node* because after reversing the linked-list they will return the pointer to the First node of the list.

Upvotes: 0

Luchian Grigore
Luchian Grigore

Reputation: 258558

You approach isn't wrong, but you might be giving too much emphasis on your linkedList class.

What does that class actually contain? A pointer to the first node, and a pointer to the last node (which is redundant information, since you can find the last node by only knowing the first one). So basically linkedList is just a helper class with no extra information.

The member functions from linkedList could easily be moved inside Node or made free functions that take a Node as parameter.

Upvotes: 4

paxdiablo
paxdiablo

Reputation: 881153

Well, what is a linked list but a pointer to the first node? A list is fully accessible provided you can get to the first node, and all you need for that is a pointer to the first node.

Unless you want to store extra control information about the list (such as its length for example), there's no need for a separate data type for the list itself.

Now some implementations (such as yours) may also store a pointer to the last node in the list for efficiency, allowing you to append an item in O(1) instead of O(n). But that's an extra feature for the list, not a requirement of lists in general.

Upvotes: 2

Related Questions