ScaleFree

DS & A (Lists - Pointer Based)

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;

  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 setBegin() = 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. };

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;

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

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

  24.     public:

  25.     LList()
  26.     {
  27.         fence = tail = head = new Node<e>;
  28.         left_length = right_length= 0;
  29.     }

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


  5. template<typename e> 
  6. bool LList<e>::insert(const e& item) 
  7.      fence->next = new Node<e>(item,fence, fence-> next); 
  8.      if(tail == fence) tail = fence-> next; 
  9.      if (fence->next->next != nullptr) 
  10.      fence->next->next->prev = fence->next; 
  11.      right_length++; 
  12.      return true; 


  13. template<typename e> 
  14. bool LList<e>::append(const e& item) 
  15.      tail->next = new Node<e>(item,tail,tail->next); 
  16.      tail = tail->next; 
  17.      right_length++; 
  18.      return true; 


  19. template<typename e> 
  20. bool LList<e>::remove(e& item) 
  21.      if (fence->next == nullptr) return false; 
  22.      item = fence->next->element; 
  23.      Node<e>* temp = fence->next; 
  24.      if(temp->next == nullptr) 
  25.      tail = fence; 
  26.      else 
  27.      temp->next->prev = fence; 
  28.      fence->next = temp->next; 
  29.      delete temp; 
  30.      right_length--; 
  31.      return true; 

  32. template<typename e> 
  33. void LList<e>::setBegin() 
  34.      fence = head; 
  35.      right_length += left_length; 
  36. left_length = 0; 

  37. template<typename e> 
  38. void LList<e>::setEnd() 
  39.      fence = tail; 
  40.      left_length += right_length; 
  41.      right_length = 0; 

  42. template<typename e> 
  43. void LList<e>::prev() 
  44.      if(fence == head) return; 
  45.      fence = fence->prev; 

  46. template<typename e> 
  47. void LList<e>::next() 
  48.      if(fence == tail) return; 
  49.      fence = fence->next; 

  50. template<typename e> 
  51. int LList<e>::leftLength() const 
  52.      return left_length; 

  53. template<typename e> 
  54. int LList<e>::rightLength() const 
  55.      return right_length; 

  56. template<typename e> 
  57. bool LList<e>::setPos(int pos) 
  58.      if(pos<0 && pos>left_length+right_length) 
  59.      { 
  60.      return false; 
  61.      } 
  62.      fence = head; 
  63.      for(int i=0; i<pos; i++) 
  64.      { 
  65.           fence = fence->next; 
  66.           left_length++; 
  67.           right_length--; 
  68.      } 
  69.      right_length = right_length+left_length-pos; 
  70.      left_length = pos; 
  71.      return true; 

  72. template<typename e> 
  73. bool LList<e>::getValue(e& item) const 
  74.      if(rightLength() == 0)      
  75.      { 
  76.           return false; 
  77.      } 
  78.      item = fence->next->element; 
  79.      return true; 

  80. template<typename e> 
  81. void LList<e>::print() const 
  82.      Node<e>* temp = head; 
  83.      std::cout<<"[ "; 
  84.      while(temp != fence)
  85.      { 
  86.           std::cout<<temp->next->element<<" "; 
  87.           temp = temp->next; 
  88.      } 
  89.      std::cout<<"| "; 
  90.      while(temp != tail) 
  91.      { 
  92.           std::cout<<temp->next->element<<" "; 
  93.           temp=temp->next; 
  94.      } 
  95.      std::cout<<"]\n"; 
  96. }

Testing the Linked List implementation

  1. int main()
  2. {
  3.     LList<int> newList; //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 because we defined the maxSize of the list to be 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 (Remember that fence position begins from 0)
  21.     std::cout<<"\nAfter setting position to 8\n";
  22.     newList.print();

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

  24.     //getting the previous value
  25.     newList.prev();                 //setting the fence to the PREVIOUS value
  26.     newList.getValue(value);        //value is passed by reference
  27.     std::cout<<"\nAccessing Previous Value: "<<value<<std::endl;

  28.     //getting the next value
  29.     newList.next();                 //setting the fence to the NEXT value
  30.     newList.getValue(value);        //value is passed by reference
  31.     std::cout<<"Accessing Next Value    : "<<value<<std::endl;

  32.     //Removing the current value at fence
  33.     newList.remove(value);          //value here will store the value of the removed item from the list
  34.     std::cout<<"\nAfter removing a value: \n";
  35.     newList.print();
  36.     std::cout<<"\nDisplaying Removed Value: "<<value<<std::endl;

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

  40.     //Inserting the removed value(i.e.,233) at the beginning of the List
  41.     newList.insert(value);
  42.     std::cout<<"\nAfter Inserting removed value to the list again:\n";
  43.     newList.print();
  44.     return 0;
  45. }

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

Share on Social Media

Most Viewed Posts

DS & A (Lists - Array Based)

SPACE & DRAGONS

DATA STRUCTURES AND ALGORITHMS