ScaleFree

DS & A (Lists - Array Based)

"The List Data Structure", Yep, that's exactly what today's chapter is gonna be about. So, without any further ado let's have a sneak peek of today's chapter.
  • Intro to Lists
  • List ADT
  • List Implementation (Array-Based)
  • Pros and Cons of Array-Based List
Pre-requisite: C++
Intro to Lists

Credits: <Link 1> <Link 2>

Definition
A list in Data Structures can be defined as a sequence of ordered values.
General Properties:
  • Can be Sorted or Unsorted
  • Can be Finite or Infinite
Note: We will be working with finite lists.
Example

  • The List is of size n.
  • Each element has a datatype
  • The List can be empty. (Empty Lists)
  • List length is the number of elements stored.
  • The beginning of the List is called Head.
  • The end of the List is called Tail.
Basic functions of a List
  1. Retrieve value.
  2. Insert/Delete/Modify value.
  3. Search for a value.
List ADT

  1. template<typename e> class List
  2. {
  3.      //Empty the list
  4.      virtual void clear() = 0;

  5.      //Insert value of e into the list at a position before the current position
  6.      virtual bool insert(const e&) = 0;

  7.      //Append e to the list
  8.      virtual bool append(const e&) = 0;

  9.      //Remove element at the current position
  10.      virtual bool remove(e&) = 0;

  11.      //set current position to the beginning
  12.      virtual void setStart() = 0;

  13.      //Set current position to the end
  14.      virtual void setEnd() = 0;

  15.      //Set current position to the previous element
  16.      virtual void prev() = 0;

  17.      //Set current position to the next element
  18.      virtual void next() = 0;

  19.      //Size of list to the left of current element
  20.      virtual int leftLength() const = 0;

  21.      //Size of list to the right of current element + 1(inclusion of current element)
  22.      virtual int rightLength() const = 0;

  23.      //Set current position to pos
  24.      virtual bool setPos(int pos) = 0;

  25.      //Get value at current position
  26.      virtual bool getValue(e& item) const = 0;

  27.      //Print list
  28.      virtual void print() const = 0;
  29. };

List Implementation
  • Array-Based List Implementation
  1. #include <iostream.h>
  2. #include "name_of_the_ListADT_file.h"

  3. template<typename e>
  4. class AList:public List<e>
  5. {
  6. private:
  7.      int maxSize;     // maximum size of list
  8.      int listSize;    // number of stored values in the list
  9.      int fence;       // position of fence
  10.      e* listArray;    // array holding list

  11. public:
  12.      AList(int size = 0)
  13.      {
  14.           maxSize = size;
  15.           listSize = fence = 0;
  16.           listArray = new e[maxSize];
  17.      }
  18.      ~AList()
  19.      {
  20.           delete []listArray;
  21.      }

  22.      //Mandatory redeclaration because these functions are pure virtual in the base class
  23.      void clear() override;
  24.      bool insert(const e&) override;
  25.      bool append(const e&) override;
  26.      bool remove(e&) override;
  27.      void setStart() override;
  28.      void setEnd() override;
  29.      void prev() override;
  30.      void next() override;
  31.      int leftLength() const override;
  32.      int rightLength() const override;
  33.      bool setPos(int pos) override;
  34.      bool getValue(e& item) const override;
  35.      void print() const override;
  36. };

  37. template<typename e>
  38. void AList<e>::clear()
  39. {
  40.      listSize = fence = 0;
  41.      delete []listArray;
  42.      listArray = new e[maxSize];
  43. }

  44. template<typename e>
  45. bool AList<e>::insert(const e& item)
  46. {
  47.      if(maxSize == listSize)
  48.      {
  49.           return false;
  50.      }
  51.      for(int i = listSize; i>fence; i--)
  52.      {
  53.           listArray[i] = listArray[i-1];
  54.      }
  55.      listArray[fence] = item;
  56.      listSize++;
  57.      return true;
  58. }

  59. template<typename e>
  60. bool AList<e>::append(const e& item)
  61. {
  62.     if(listSize == maxSize)
  63.     {
  64.         return false;
  65.     }
  66.     listArray[listSize++] = item;
  67.     return true;
  68. }

  69. template<typename e>
  70. bool AList<e>::remove(e& item)
  71. {
  72.     if(rightLength() == 0)
  73.     {
  74.         return false;
  75.     }
  76.     item = listArray[fence];
  77.     for(int i=fence; i<listSize; i++)
  78.     {
  79.         listArray[i] = listArray[i+1];
  80.     }
  81.     listSize--;
  82.     return true;
  83. }

  84. template<typename e>
  85. void AList<e>::setStart()
  86. {
  87.     fence = 0;
  88. }

  89. template<typename e>
  90. void AList<e>::setEnd()
  91. {
  92.     fence = listSize;
  93. }

  94. template<typename e>
  95. void AList<e>::prev()
  96. {
  97.     if(fence == 0) return;
  98.     fence--;
  99. }

  100. template<typename e>
  101. void AList<e>::next()
  102. {
  103.     if(fence == listSize-1) return;
  104.     fence++;
  105. }

  106. template<typename e>
  107. int AList<e>::leftLength() const
  108. {
  109.     return fence;
  110. }

  111. template<typename e>
  112. int AList<e>::rightLength() const
  113. {
  114.     return listSize-fence;
  115. }

  116. template<typename e>
  117. bool AList<e>::setPos(int pos)
  118. {
  119.     if(pos>=0 && pos<=listSize)
  120.     {
  121.         fence = pos;
  122.         return true;
  123.     }
  124.     return false;
  125. }

  126. template<typename e>
  127. bool AList<e>::getValue(e& item) const
  128. {
  129.     if(listSize == 0)
  130.     {
  131.         return false;
  132.     }
  133.     item = listArray[fence];
  134.     return true;
  135. }

  136. template<typename e>
  137. void AList<e>::print() const
  138. {
  139.     std::cout<<"[ ";
  140.     for(int i=0; i<listSize; i++)
  141.     {
  142.         std::cout<<((i==fence)?"| ":"")<<listArray[i]<<((i==listSize-1)?" ]\n":", ");
  143.     }
  144. }
  • Array-Based List Structure Visualization
  • Testing the Array-Based list implementation
  1. int main()
  2. {
  3.     AList<int> newList(10); //creating a list object

  4.     //Adding values to the list
  5.     newList.append(1);
  6.     newList.append(12);
  7.     newList.append(21);
  8.     newList.append(132);
  9.     newList.append(321);
  10.     newList.append(89);
  11.     newList.append(567);
  12.     newList.append(43);
  13.     newList.append(233);
  14.     newList.append(67);

  15.     //The following values won't be added to the list since maxSize = 10

  16.     newList.append(33);
  17.     newList.append(54);
  18.     newList.append(78);

  19.     newList.print();

  20.     newList.setPos(8);              //changing the position of the fence 
  21.     std::cout<<"\nAfter setting position to 8\n";
  22.     newList.print();
  23.     
  24.     int value;                      //temporary variable to store values
  25.     
  26.     //getting the previous value
  27.     
  28.     newList.prev();                 //setting the fence to the PREVIOUS value     
  29.     newList.getValue(value);        //value is passed by reference     
  30.     std::cout<<"\nAccessing Previous Value: "<<value<<std::endl;      
  31.     
  32.     //getting the next value     
  33.     
  34.     newList.next();                 //setting the fence to the NEXT value     
  35.     newList.getValue(value);        //value is passed by reference     
  36.     std::cout<<"Accessing Next Value    : "<<value<<std::endl;      
  37.     
  38.     //Removing the current value at the fence     
  39.     
  40.     newList.remove(value);          //stores the value of the removed item    
  41.     std::cout<<"\nAfter removing a value: \n";     
  42.     newList.print();     
  43.     std::cout<<"\nDisplaying Removed Value: "<<value<<std::endl;      
  44.     newList.setStart();             //sets the fence to the beginning of the list     
  45.     std::cout<<"\nAfter setting position to the start:\n";     
  46.     newList.print();      
  47.     
  48.     //Inserting the removed value(i.e.,233) at the beginning of the List     
  49.     
  50.     newList.insert(value);     
  51.     std::cout<<"\nAfter Inserting removed value to the list again:\n";     
  52.     newList.print();     
  53.     return 0;
  54. }

Pros and Cons Of  Pointer-Based List
Pros:
  • No overhead if all array positions are filled. (Overhead is the amount of memory needed to maintain a data structure).
Cons:
  • The array must be allocated in advance.
  • Waste of memory if all array positions are not filled.
( If you like the content here, follow TSP on social media to get notified on future updates)



Comments

Share on Social Media

Most Viewed Posts

SPACE & DRAGONS

DATA STRUCTURES AND ALGORITHMS