EECE 330 Chapter, Fall 2011

EECE 330 Data Structures & Algorithms Singly-Linked Lists Singly-Linked Lists © Hassan Artail American University of Beirut Lists A list is a finite, ordered sequence of data items. Important concept: List elements have a position. Notation: <a0, a1, …, an-1> What operations should we implement? List Implementation Concepts The list implementation will support the concept of a current position. We do this by defining the list in terms of left and right partitions. • Either or both partitions may be empty. Partitions are separated by the fence. <20, 23 | 12, 15> List ADT template <class Elem> class List { public: virtual void clear() = 0; virtual bool insert(const Elem&) = 0; virtual bool append(const Elem&) = 0; virtual bool remove(Elem&) = 0; virtual void setStart() = 0; virtual void setEnd() = 0; virtual void prev() = 0; virtual void next() = 0; List ADT (cont) virtual int leftLength() const = 0; virtual int rightLength() const = 0; virtual bool setPos(int pos) = 0; virtual bool getValue(Elem&) const = 0; virtual void print() const = 0; }; List ADT Examples List: < , 32, 15> MyList.insert(99); Result: < , 99, 32, 15> Iterate through the whole list: for (MyList.setStart(); MyList.getValue(it); MyList.next()) DoSomething(it); 12 12 List Find Function // Return true iff K is in list bool find(List<int>& L, int K) { int it; for (L.setStart(); L.getValue(it); L.next()) if (K == it) return true; // Found it return false; // Not found } Array-Based List Insert Array-Based List Class (1) template <class Elem> // Array-based list class AList : public List<Elem> { private: int maxSize; // Maximum size of list int listSize; // Actual elem count int fence; // Position of fence Elem* listArray; // Array holding list public: AList(int size=DefaultListSize) { maxSize = size; listSize = fence = 0; listArray = new Elem[maxSize]; } Array-Based List Class (2) ~AList() { delete [] listArray; } void clear() { delete [] listArray; listSize = fence = 0; listArray = new Elem[maxSize]; } void setStart() { fence = 0; } void setEnd() { fence = listSize-1; } void prev() { if (fence != 0) fence--; } void next() { if (fence < listSize) fence++; } int leftLength() const { return fence+1; } int rightLength() const { return listSize – fence -1; } Array-Based List Class (3) bool setPos(int pos) { if ((pos >= 0) && (pos < listSize)) fence = pos; return (pos >= 0) && (pos < listSize); } bool getValue(Elem& it) const { if (rightLength() == 0) return false; else { it = listArray[fence+1]; return true; } } }; Insert // Insert at front of right partition template <class Elem> bool AList<Elem>::insert(const Elem& item) { if (listSize == maxSize) return false; for(int i=listSize; i>fence; i--) // Shift Elems up to make room listArray[i] = listArray[i-1]; listArray[fence+1] = item; listSize++; // Increment list size return true; } Append // Append Elem to end of the list template <class Elem> bool AList<Elem>::append(const Elem& item) { if (listSize == maxSize) return false; listArray[listSize++] = item; return true; } Remove // Remove and return first Elem in right partition template <class Elem> bool AList<Elem>::remove(Elem& it) { if (rightLength() == 0) return false; it = listArray[fence]; // Copy Elem for(int i=fence; i<listSize-1; i++) // Shift them down listArray[i] = listArray[i+1]; // Decrement size listSize--; return true; } Link Class Dynamic allocation of new list elements // Singly-linked list node template <class Elem> class Link { public: Elem element; // Value for this node Link *next; // Pointer to next node //First Constructor Link(const Elem& elemval, Link* nextval =NULL) { element = elemval; next = nextval; } //Overloaded Constructor Link(Link* nextval =NULL) { next = nextval; } }; Linked List Position (2) Linked List Class (1) // Linked list implementation template <class Elem> class LList: public List<Elem> { private: Link<Elem>* head; // Point to list header Link<Elem>* tail; // Pointer to last Elem Link<Elem>* fence;// Last element on left int leftcnt; // Size of left int rightcnt; // Size of right void init() { // Intialization routine fence = tail = head = new Link<Elem>; leftcnt = rightcnt = 0; } Linked List Class (2) void removeall() { // Return link nodes to free store while(head != NULL) { fence = head; head = head->next; delete fence; } } public: LList(int size=DefaultListSize) { init(); } ~LList() { removeall(); } // Destructor void clear() { removeall(); init(); } Linked List Class (3) void setStart() { fence = head; rightcnt += leftcnt; leftcnt = 0; } void setEnd() { fence = tail; leftcnt += rightcnt; rightcnt = 0; } void next() { // Don't move fence if right empty if (fence != tail) { fence = fence->next; rightcnt--; leftcnt++; } } int leftLength() const { return leftcnt; } int rightLength() const { return rightcnt; } bool getValue(Elem& it) const { if(rightLength() == 0) return false; it = fence->next->element; return true; } }; Insertion Insert/Append // Insert at front of right partition template <class Elem> bool LList<Elem>::insert(const Elem& item) { fence->next = new Link<Elem>(item, fence->next); if (tail == fence) tail = fence->next; rightcnt++; return true; } // Append Elem to end of the list template <class Elem> bool LList<Elem>::append(const Elem& item) { tail = tail->next = new Link<Elem>(item, NULL); rightcnt++; return true; } Removal Remove // Remove and return first Elem in right partition template <class Elem> bool LList<Elem>::remove(Elem& it) { if (fence->next == NULL) return false; it = fence->next->element; // Remember value // Remember link node Link<Elem>* ltemp = fence->next; fence->next = ltemp->next; // Remove if (tail == ltemp) // Reset tail tail = fence; delete ltemp; // Reclaim space rightcnt--; return true; } Prev // Move fence one step left; no change if left is empty template <class Elem> void LList<Elem>::prev() { Link<Elem>* temp = head; if (fence == head) return; // No prev Elem while (temp->next!=fence) temp=temp->next; fence = temp; leftcnt--; rightcnt++; } Setpos // Set the size of left partition to pos template <class Elem> bool LList<Elem>::setPos(int pos) { if ((pos < 0) || (pos > rightcnt+leftcnt)) return false; fence = head; for(int i=0; i<pos; i++) fence = fence->next; return true; } Comparison of Implementations Array-Based Lists: • Insertion and deletion are (n). • Prev and direct access are (1). • Array must be allocated in advance. • No overhead if all array positions are full. Linked Lists: • Insertion and deletion are (1). • Prev and direct access are (n). • Space grows with number of elements. • Every element requires overhead.