ScaleFree

DS & A (Lists - Pointer Based)

By

| CHAPTER 10 |

Pre-requisite: C++, Knowledge on Pointers

 Two ways of implementing lists using pointers:
  • Doubly Linked Linked List
  • Singly Linked List

List ADT

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

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

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

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

  15.      //set current position to the beginning
  16.      virtual void setBegin() = 0;

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

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

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

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

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

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

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

  39.      //Print list
  40.      virtual void print() const = 0;
  41. };

Doubly Linked List Implementation
  • Creating the Node

  1. template <typename e> class Node
  2. {
  3. public:
  4.     e element;
  5.     Node<e>* next;
  6.     Node<e>* prev;

  8.     Node(const e& elemValue,Node<e>* prevPtr = nullptr, Node<e>* nextPtr = nullptr)
  9.     {
  10.         element = elemValue;
  11.         prev = prevPtr;
  12.         next = nextPtr;
  13.     }
  14.     Node(Node<e>* prevPtr = nullptr, Node<e>* nextPtr = nullptr)
  15.     {
  16.         prev = prevPtr;
  17.         next = nextPtr;
  18.     }
  19. };

  21. template<typename e> class LList:public List<e>
  22. {
  23.     private:
  24.     Node<e>* head, *tail, *fence;
  25.     int left_length, right_length;

  27.     public:

  29.     LList()
  30.     {
  31.         fence = tail = head = new Node<e>;
  32.         left_length = right_length= 0;
  33.     }

  35.     bool insert(const e&) override;
  36.     bool append(const e&) override;
  37.     void setBegin() override;
  38.     void setEnd() override;
  39.     int leftLength() const override;
  40.     int rightLength() const override;
  41.     void prev() override;
  42.     void next() override;
  43.     bool remove(e&) override;
  44.     void clear() override;
  45.     bool setPos(int pos) override;
  46.     bool getValue(e& item) const override;
  47.     void print() const override;
  48. };
  • The Implementation
  1. template<typename e> 
  2. void LList<e>::clear() 
  3. { 
  4.      delete fence,tail,head; 
  5.      LList(); 
  6. } 


  9. template<typename e> 
  10. bool LList<e>::insert(const e& item) 
  11. { 
  12.      fence->next = new Node<e>(item,fence, fence-> next); 
  13.      if(tail == fence) tail = fence-> next; 
  14.      if (fence->next->next != nullptr) 
  15.      fence->next->next->prev = fence->next; 
  16.      right_length++; 
  17.      return true; 
  18. } 


  21. template<typename e> 
  22. bool LList<e>::append(const e& item) 
  23. { 
  24.      tail->next = new Node<e>(item,tail,tail->next); 
  25.      tail = tail->next; 
  26.      right_length++; 
  27.      return true; 
  28. } 


  31. template<typename e> 
  32. bool LList<e>::remove(e& item) 
  33. { 
  34.      if (fence->next == nullptr) return false; 
  35.      item = fence->next->element; 
  36.      Node<e>* temp = fence->next; 
  37.      if(temp->next == nullptr) 
  38.      tail = fence; 
  39.      else 
  40.      temp->next->prev = fence; 
  41.      fence->next = temp->next; 
  42.      delete temp; 
  43.      right_length--; 
  44.      return true; 
  45. } 

  47. template<typename e> 
  48. void LList<e>::setBegin() 
  49. { 
  50.      fence = head; 
  51.      right_length += left_length; 
  52. left_length = 0; 
  53. } 

  55. template<typename e> 
  56. void LList<e>::setEnd() 
  57. { 
  58.      fence = tail; 
  59.      left_length += right_length; 
  60.      right_length = 0; 
  61. } 

  63. template<typename e> 
  64. void LList<e>::prev() 
  65. { 
  66.      if(fence == head) return; 
  67.      fence = fence->prev; 
  68. } 

  70. template<typename e> 
  71. void LList<e>::next() 
  72. { 
  73.      if(fence == tail) return; 
  74.      fence = fence->next; 
  75. } 

  77. template<typename e> 
  78. int LList<e>::leftLength() const 
  79. { 
  80.      return left_length; 
  81. } 

  83. template<typename e> 
  84. int LList<e>::rightLength() const 
  85. { 
  86.      return right_length; 
  87. } 

  89. template<typename e> 
  90. bool LList<e>::setPos(int pos) 
  91. { 
  92.      if(pos<0 && pos>left_length+right_length) 
  93.      { 
  94.      return false; 
  95.      } 
  96.      fence = head; 
  97.      for(int i=0; i<pos; i++) 
  98.      { 
  99.           fence = fence->next; 
  100.           left_length++; 
  101.           right_length--; 
  102.      } 
  103.      right_length = right_length+left_length-pos; 
  104.      left_length = pos; 
  105.      return true; 
  106. } 

  108. template<typename e> 
  109. bool LList<e>::getValue(e& item) const 
  110. { 
  111.      if(rightLength() == 0)      
  112.      { 
  113.           return false; 
  114.      } 
  115.      item = fence->next->element; 
  116.      return true; 
  117. } 

  119. template<typename e> 
  120. void LList<e>::print() const 
  121. { 
  122.      Node<e>* temp = head; 
  123.      std::cout<<"[ "; 
  124.      while(temp != fence)
  125.      { 
  126.           std::cout<<temp->next->element<<" "; 
  127.           temp = temp->next; 
  128.      } 
  129.      std::cout<<"| "; 
  130.      while(temp != tail) 
  131.      { 
  132.           std::cout<<temp->next->element<<" "; 
  133.           temp=temp->next; 
  134.      } 
  135.      std::cout<<"]\n"; 
  136. }

Testing the Linked List implementation

  1. int main()
  2. {
  3.     LList<int> newList; //creating a list object

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

  17.     //The following values won't be added to the list because we defined the maxSize of the list to be 10
  18.     newList.append(33);
  19.     newList.append(54);
  20.     newList.append(78);

  22.     newList.print();

  24.     newList.setPos(8);              //changing the position of the fence (Remember that fence position begins from 0)
  25.     std::cout<<"\nAfter setting position to 8\n";
  26.     newList.print();

  28.     int value;                      //temporary variable to store values

  30.     //getting the previous value
  31.     newList.prev();                 //setting the fence to the PREVIOUS value
  32.     newList.getValue(value);        //value is passed by reference
  33.     std::cout<<"\nAccessing Previous Value: "<<value<<std::endl;

  35.     //getting the next value
  36.     newList.next();                 //setting the fence to the NEXT value
  37.     newList.getValue(value);        //value is passed by reference
  38.     std::cout<<"Accessing Next Value    : "<<value<<std::endl;

  40.     //Removing the current value at fence
  41.     newList.remove(value);          //value here will store the value of the removed item from the list
  42.     std::cout<<"\nAfter removing a value: \n";
  43.     newList.print();
  44.     std::cout<<"\nDisplaying Removed Value: "<<value<<std::endl;

  46.     newList.setBegin();             //sets the fence to the beginning of the list
  47.     std::cout<<"\nAfter setting position to the begin:\n";
  48.     newList.print();

  50.     //Inserting the removed value(i.e.,233) at the beginning of the List
  51.     newList.insert(value);
  52.     std::cout<<"\nAfter Inserting removed value to the list again:\n";
  53.     newList.print();
  54.     return 0;
  55. }

Singly Linked List Implementation

I leave that to you guys as an exercise. Try implementing it. All the best...
OR
You can join our Facebook group for the code

Pros and Cons Of  Array-Based List

Pros:
  • List size is not fixed. Hence, pre-allocation of memory is not necessary.
Cons:
  • Every element requires overhead.
  • Element access is complicated. Elements can't be accessed through indices.
( If you like the content here, follow TSP on social media to get notified on future updates)


Comments

Post a Comment

Share on Social Media

Most Viewed Posts

DS & A (Algorithm Analysis - Best, Worst and Average Case)

By
Image
|  CHAPTER 5  | Note: If it's your first time visiting this website I strongly recommend you to read the previous chapter before reading this chapter. Till now we learned about what Data Structures and Algorithms are, some basic terminologies and a few  concepts  of Algorithm analysis.   And continuing our ongoing journey of Data Structures and Algorithms, today we will discuss the Best Case, Average Case and Worst Case of an algorithm. Algorithm Case Analysis In the last chapter, we learned that every algorithm has running time[T(n)] and a growth rate. But that's not the end of it, an algorithm's running time and growth rate are not the only factors that we should consider while designing an algorithm. For some algorithms, different inputs result in different running time. And that brings forth the necessity of the concept of Best, Average, and Worst Case of algorithms. Example Consider we have four boxes tagged 1,2,3 & 4, and the boxes con
Read more

SPACE & DRAGONS

By
Image
Space and Dragons is a top-down endless space shooter where the player takes on the role of a brave space warrior. In the game, the player has to fight against fierce Space Dragons while making the way through other obstacles such as space debris and much more. FEATURES: SPACE DRAGONS MOVING DEBRIS POWER-UPS HEALTH BOOST SHIELD AND much more SCREENSHOTS...... APPLICATIONS USED : QT Creator (A C++ based framework) GIMP (An Image Manipulation Software) AUDACITY (An Audio Manipulation Software) NOTE: The game resources have been collected from the OpenGameArt website and various other online sources. The used game assets are not my property. GAME DOWNLOAD LINK: DOWNLOAD GAME GAME REQUIREMENTS OS : WINDOWS RAM : 1 GB HARD DRIVE : 150 MB CONTROLS: LEFT, RIGHT keys for movements and SPACE to Shoot SPACE SHOOTER IN ACTION UPDATE << Click here to download the source code >> Zip Password: TheSuperProgrammer NOTE: The game
Read more

DS & A(Queue)

By
Image
|  CHAPTER 14  | In this chapter, our topic of discussion will be the "Queue" Data Structure. But, before we get started, I would recommend you to read the previous chapters on Data Structures & Algorithms  (especially the chapters on Array List , Linked List , Array Stack , and Linked Stack ), that is in case it's your first time visiting my blog. Queue: Just like Stacks, Queues also are a restricted version of List but with a few minor differences compared to Stack. The following are some of the notable characteristics of a Queue: Data can only be inserted from the rear/back. Data insertion is referred to as  ENQUEUE . Data can only be deleted from the front. Data deletion is referred to as  DEQUEUE . Alternatively,  ENQUEUE  and  DEQUEUE  should always be executed on the opposite ends of the Queue. A Queue follows the  FIFO (First In First Out)   principle. The first and the last elements are referred to as FRONT and REAR respectively.
Read more