CODEWITHSUNDEEP
c++
James Cornod
James Cornod

Reputation: 39

Indexed singly linked list

I want to create a singly linked list with. I already have an implementation that does not permit indexing on it. I would like to add this feature but I am not sure how to do that.

Linked List

So basically the head should have index "1". But I can't figure it out myself what am I supposed to do in If statement to increase the index by 1 each step.

void AddNode (int addData)
{
    nodePtr NewNode = new node;
    NewNode->next = NULL;
    NewNode->data = addData;

    if (head != NULL)
    {
        curr = head;
        while(curr->next != NULL)
        {
            curr = curr->next;
        }
        curr->next = NewNode;
        NewNode->index;
    }
    else
    {
        head = NewNode;
        NewNode->index = 1;
    }
}

Upvotes: 0

Views: 3550

Answers (3)

Davide Spataro
Davide Spataro

Reputation: 7482

So what you really want to do is to add the ability to index elements of a linked list.

  • There is no need to actually store the index anywhere (as you don't really store the index of an array/vector element as the type and the address of the first element of the array is everything you need to retrieve the i-th element).

  • The only information you want to keep is the length of the list since computing it is costly because you have to traverse the list from head to tail every time you need it. Once you have this information the addNode should only update the size of the list.

As you already know accessing the i-th elements of a linked list is also costly (compared to a vector), but it is easy to code.

Something like the following should work:

void get(Node* head, size_t pos) {
    while (head && pos--)
        head = head->next;
    return pos<=0 ? head : nullptr ;
}

It traverses the list from the head until it either reaches the end (head is nullptr) or pos is <=0. Once you are out of the loop if pos>0 means that the list is shorter than pos otherwise you can return head (which will point to the pos-th element)

Upvotes: 0

astrade
astrade

Reputation: 222

You mean for the ability to do something like get a linked list node via a get(index)?

Also, your head should not have index 1, it should be 0. This does not comply with standard practice of zero-based indexing.

A linked list does not technically have indexes nor should it store them. It seems like a linked list might not be the right data structure for what you are doing, however you can treat it like so with a loop like this (excuse if my c++ syntax is rusty)

int get(int index) {
  Node current = head;
  for (int x = 0; x < index; x++) {
    if (current->next == null) {
      //some sort of error handling for index out of bounds
    } else {
      current = current->next;
    }
  }
  return current->data
}

get(2) would return the 3rd element of the list.

Upvotes: 3

yao
yao

Reputation: 1

Graph for the structure Why do you want to add it to the end of the list? Just simply add the new node to the front.

I don't think it is necessary to follow the order of 1,2,3.... Instead, you can do it reversely Before you add a new node, you visit the head and find the index(i)of it. When you add the new one, the index of this one will be i+1.

Two advantages: - It doses not change anything when you loop through this list. - You know how many you have added into this list.

Upvotes: 0

Related Questions