1: // The copy constructor and the method setEntry are left as exercises.
2: // ===================================================================
4: // Created by Frank M. Carrano and Tim Henry.
5: // Copyright (c) 2013 __Pearson Education__. All rights reserved.
7: /** Implementation file for the class LinkedList.
8: @file LinkedList.cpp */
10: #include "LinkedList.h" // Header file
11: #include <cassert>
12:
13: template<class ItemType>
14: LinkedList<ItemType>::LinkedList() : headPtr(nullptr), itemCount(0)
15: {
16: } // end default constructor
18: template<class ItemType>
19: LinkedList<ItemType>::~LinkedList()
20: {
21: clear();
22: } // end destructor
24: template<class ItemType>
25: bool LinkedList<ItemType>::isEmpty() const
26: {
27: return itemCount == 0;
28: } // end isEmpty
30: template<class ItemType>
31: int LinkedList<ItemType>::getLength() const
32: {
33: return itemCount;
34: } // end getLength
36: template<class ItemType>
37: bool LinkedList<ItemType>::insert(int newPosition, const ItemType& newEntry)
38: {
39: bool ableToInsert = (newPosition >= 1) && (newPosition <= itemCount + 1);
40: if (ableToInsert)
41: {
42: // Create a new node containing the new entry
43: Node<ItemType>* newNodePtr = new Node<ItemType>(newEntry);
44:
45: // Attach new node to chain
46: if (newPosition == 1)
47: {
48: // Insert new node at beginning of chain
49: newNodePtr->setNext(headPtr);
50: headPtr = newNodePtr;
51: }
52: else
53: {
54: // Find node that will be before new node
55: Node<ItemType>* prevPtr = getNodeAt(newPosition - 1);
56:
57: // Insert new node after node to which prevPtr points
58: newNodePtr->setNext(prevPtr->getNext());
59: prevPtr->setNext(newNodePtr);
60: } // end if
62: itemCount++; // Increase count of entries
63: } // end if
64:
65: return ableToInsert;
66: } // end insert
68: template<class ItemType>
69: bool LinkedList<ItemType>::remove(int position)
70: {
71: bool ableToRemove = (position >= 1) && (position <= itemCount);
72: if (ableToRemove)
73: {
74: Node<ItemType>* curPtr = nullptr;
75: if (position == 1)
76: {
77: // Remove the first node in the chain
78: curPtr = headPtr; // Save pointer to node
79: headPtr = headPtr->getNext();
80: }
81: else
82: {
83: // Find node that is before the one to delete
84: Node<ItemType>* prevPtr = getNodeAt(position - 1);
85:
86: // Point to node to delete
87: curPtr = prevPtr->getNext();
88:
89: // Disconnect indicated node from chain by connecting the
90: // prior node with the one after
91: prevPtr->setNext(curPtr->getNext());
92: } // end if
93:
94: // Return node to system
95: curPtr->setNext(nullptr);
96: delete curPtr;
97: curPtr = nullptr;
98:
99: itemCount--; // Decrease count of entries
100: } // end if
101:
102: return ableToRemove;
103: } // end remove
105: template<class ItemType>
106: void LinkedList<ItemType>::clear()
107: {
108: while (!isEmpty())
109: remove(1);
110: } // end clear
112: template<class ItemType>
113: ItemType LinkedList<ItemType>::getEntry(int position) const throw(PrecondViolatedExcep)
114: {
115: // Enforce precondition
116: bool ableToGet = (position >= 1) && (position <= itemCount);
117: if (ableToGet)
118: {
119: Node<ItemType>* nodePtr = getNodeAt(position);
120: return nodePtr->getItem();
121: }
122: else
123: {
124: string message = "getEntry() called with an empty list or ";
125: message = message + "invalid position.";
126: throw(PrecondViolatedExcep(message));
127: } // end if
128: } // end getEntry
130: template<class ItemType>
131: Node<ItemType>* LinkedList<ItemType>::getNodeAt(int position) const
132: {
133: // Debugging check of precondition
134: assert( (position >= 1) && (position <= itemCount) );
135:
136: // Count from the beginning of the chain
137: Node<ItemType>* curPtr = headPtr;
138: for (int skip = 1; skip < position; skip++)
139: curPtr = curPtr->getNext();
140:
141: return curPtr;
142: } // end getNodeAt
143: // End of implementation file.