0

I have a double link list using arrays and while inserting elements I maintain order, something like this. I am treating new values (nodes) as array indices and store them directly to their location. The link list is quite long. Everything is working as required but is there any algorithm or ideas that can help me to reduce number of iterations when a node falls between head and tail?

That is

if (new_node > head && new_node < tail) {
        search from head() 
}

So to reduce iteration; I added search from tail() after finding new-node is closer to which head or tail. Then I added a mid-node that is somewhere in mid of head and tail. But still I am still not able to reduce iterations when node needs to be linked. Will knowing range of values help? What else can be done to reduce number of iteration while inserting (due to sorted nature)?

I hope I am able to explain this properly.

Aval Sarri
  • 198
  • 2
  • 13
  • 1
    If it is a linked list, you should abstract it by implementing basic linked list operations. Then use them to traverse/search the list. – Eugene Sh. Sep 24 '21 at 13:23
  • 1
    You can't significantly reduce the time complexity of searching through a linear data structure. You could add special random 'shortcut' links to some nodes within the list, that would allow you to jump far forward and backward, but that significantly complicates the structure of nodes (a node essentially needs to keep a list of additional links). You might also consider som random-access list, mentioned in Wikipedia ([Linked list / Random-access lists](https://en.wikipedia.org/wiki/Linked_list#Random-access_lists)) but I have no source to point at. – CiaPan Sep 24 '21 at 13:28
  • 1
    May be you should consider a tree instead...? – CiaPan Sep 24 '21 at 13:28

1 Answers1

0

Here is a SO answer discussing the difference between array and linked list: insert/delete functions.

tldr; It is a limitation of double linked lists. Even if you wrap it inside an array to do stuff.

Understanding the underlying methods of how a linked list and array works will help identify the impossible issue you are solving. Unless you utilize a different structure, you will typically have the issues you are describing.

I would do the following:

  • Consider your problem, what do you CARE about
    • Searching?
    • Insert/Delete?
    • Memory size?
  • Then decide a data structure that best solves your problem
    • Array
    • Linked List
    • Trees
    • Hash
Frebreeze
  • 202
  • 3
  • 10