CODEWITHSUNDEEP
c++sortingdata-structures
Guido Tarsia
Guido Tarsia

Reputation: 2162

Fixed length structure re-arrange: should I use array or linked list?

This structure will only contain exactly 256 unsigned chars. The only operation possible is taking random characters from it and putting them in front of the structure. For example:

A= 'abcdef'

Move character 2 to front

A= 'cabdef'

I first thought of using linked link so that it could work as a queue. Thing is I heard that arrays are much faster than linked lists for these operations. Is this true?

Upvotes: 1

Views: 277

Answers (6)

user195488
user195488

Reputation:

In C++, you can use a vector instead of array or linked list. The complexity of a Linked List is O(1) like @Mark Ransom said. With the vector, you can use the command rotate to perform the action you desire. The complexity is determined by the number of swaps.

From MSDN, how to use rotate:

   const int VECTOR_SIZE = 8;

   // Define a template class vector of strings
   typedef vector<string> StrVector;

   //Define an iterator for template class vector of strings
   typedef StrVector::iterator StrVectorIt;

   StrVector Tongue_Twister(VECTOR_SIZE);

   StrVectorIt start, end, middle, it;

   // location of first element of Tongue_Twister
   start = Tongue_Twister.begin();   

   // one past the location last element of Tongue_Twister
   end = Tongue_Twister.end();       


   // Initialize vector Tongue_Twister
   Tongue_Twister[0] = "she";
   Tongue_Twister[1] = "sells";
   Tongue_Twister[2] = "sea";
   Tongue_Twister[3] = "shells";
   Tongue_Twister[4] = "by";
   Tongue_Twister[5] = "the";
   Tongue_Twister[6] = "sea";
   Tongue_Twister[7] = "shore";

   middle = start + 3;  // start position for rotating elements

   cout << "Before calling rotate" << endl;

   // print content of Tongue_Twister
   cout << "Try this Tongue Twister:";
   for (it = start; it != end; it++)
      cout << " " << *it;

   // rotate the items in the vector Tongue_Twister by 3 positions
   rotate(start, middle, end);

Or you can do it with arrays:

// create an array of 9 elements and rotate the entire array.
int myArray[SIZE] = { 7, 8, 9, 1, 2, 3, 4, 5, 6,  };
std::rotate(myArray, myArray + 3, myArray + SIZE);

How fast is this? I don't know. I haven't benchmarked it. But it is much easier than having to manually swap elements of an array.

Upvotes: 1

Kerrek SB
Kerrek SB

Reputation: 477040

A linked list would be a good approach since you don't need to move all the intermediate elements around. std::list works just fine, combined with splice(). You will need an iterator to the element you want to move to the front:

#include <list>
#include <iostream>
#include "prettyprint.hpp"

int main()
{
  std::list<int> x { 1, 4, 6, 7, 2 };
  auto i = x.begin(); std::advance(i, 2);  // i points to 6

  std::cout << x << std::endl;  //  [1, 4, 6, 7, 2]

  x.splice(x.begin(), x, i);

  std::cout << x << std::endl;  //  [6, 1, 4, 7, 2]
}

(Using the pretty printer for a quick demo.)

As others have said, whether that's more efficient that a random-access container depends on how you are tracking the element that you want to move.

Update: In light of Steve's remarks I should like to offer a raw C-array solution, too. It has the benefit that you can access it by position in O(1) time and that it requires minimum space:

char y[] = { 'a', 'c', 'Q', '%', '5' };
std::cout << pretty_print_array(y) << std::endl; // [a, c, Q, %, 5]
std::rotate(y, y + 2, y + sizeof(y));
std::cout << pretty_print_array(y) << std::endl; // [Q, %, 5, a, c]

The rotate call could be wrapped in a function:

template <typename T, size_t N>
void bring_forward(T (& a)[N], size_t p) { std::rotate(a, a + p, a + N); }

Upvotes: 1

Steve Townsend
Steve Townsend

Reputation: 54148

Use an array. The linked list will be huge and unwieldy for storage of char data.

Upvotes: 1

Rob Kennedy
Rob Kennedy

Reputation: 163277

The array will be O(1) to find the item and O(n) to move it and the other items into the correct position. The linked list will be O(n) to find the item and O(1) to move everything to the right position. The complexity is the same either way.

They're both easy to implement, so implement both of them and run tests to see which one lets your program run faster with real-world data.

Upvotes: 0

r3c
r3c

Reputation: 498

C++ arrays are linked lists, so moving an element to the front of your list is cheap, provided you already know where the element is (i.e. you have an iterator on it). Using a vector would cause the entire list to be shifted each time an element is pushed in front of it.

Upvotes: -2

Mark Ransom
Mark Ransom

Reputation: 308168

A linked list will be O(1) and an array will be O(n) for a move operation as you have described. For small n the array will probably be faster, but the only way to know for sure is to benchmark.

In a case like this I would code what's clearest and only worry about efficiency if it proves to be a bottleneck.

P.S. I made an assumption that you already had a pointer to the character you want to move. If this is not the case, then finding the character will be O(n) in the linked list and you will lose any advantages it might have.

Upvotes: 3

Related Questions