1
$\begingroup$

Okay, so I have been doing competitive programming for the past few days in C++. And day before yesterday, I stumbled upon this concept of linked list.

Now, what I do while implementing most problems pertaining to linked list is that I store all the values of the linked list nodes in a vector, and do operations on them which has been asked as per the question, then refill the nodes with the newly updated values of the vector. Now, most of the questions can be done by me really easily, as I am pretty comfortable with using vectors now. I just wanted to ask this community if this was a bad approach towards using linked list, and should I stop using it altogether.

I will give an example to sort a linked list in $O(N\log N)$ time, which I used. Following is a function that sorts a linked list-

ListNode* Solution::sortList(ListNode* A) {
    vector<int> vect;
    ListNode* temp=A;
    while(A!=NULL)
    {
        vect.push_back(A->val);
        A=A->next;
    }
    A=temp;
    sort(vect.begin(), vect.end());
    for(int i=0; i<vect.size(); i++)
    {
        A->val=vect[i];
        A=A->next;
    }
    return temp;
}
$\endgroup$
  • 1
    $\begingroup$ Why use linked lists at all? Their only benefit is that if you have a pointer to an element, then you can insert an element in front of it very quickly. Unless you're using something of that sort, there is really no reason to use them. If all you intend to do is to convert them to a vector and back, why not just use vector? $\endgroup$ – Yuval Filmus Apr 9 at 10:37
  • $\begingroup$ The question seems borderline off-topic, but I'm not entirely sure. $\endgroup$ – Yuval Filmus Apr 9 at 10:37
  • $\begingroup$ Yuval Filmus, only because the questions that I do demand that Linked Lists should be used to solve the question! $\endgroup$ – ammo1 Apr 9 at 11:21
  • 2
    $\begingroup$ You are not using Linked Lists to solve the questions. You are using vectors to solve them. You are defeating the purpose of the questions. $\endgroup$ – Yuval Filmus Apr 9 at 11:25
  • 1
    $\begingroup$ Some sorting algorithms lend themselves much better to linked lists, for example merge sort, which can be implemented directly using linked lists. This is more in the spirit of this actual question. $\endgroup$ – Yuval Filmus Apr 9 at 11:26
2
$\begingroup$

Let's show that $\{a^n b^n : n \geq 0\}$ is not regular using Myhill's criterion (there are infinitely many equivalence classes):

The pumping lemma shows that $\{a^n b^n : n \geq 0\}$ is not regular. According to Myhill's criterion, if a language is not regular then it has infinitely many equivalence classes. Therefore the language has infinitely many equivalence classes, and consequently, by Myhill's criterion is not regular.

This may sound silly, but it is very similar to how you are using vectors to solve questions "using linked lists".

The alternative is to look for algorithms that can be implemented directly on linked lists. For example, one sorting algorithm which can be implemented directly is merge sort. Merge sort consists of the following operations:

  • Divide the input into two sublists of nearly equal size. Easy to do on a linked list using a simple scan.
  • Recursively sort each sublist.
  • Merge the two sorted sublists. The merge algorithm is also easy to implement on a linked list.

In contrast, an algorithm like quicksort seems hard to implement directly without having random access.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.