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: headPtr = insertNode(newPosition, newNodePtr, headPtr);
45: } // end if
46:
47: return ableToInsert;
48: } // end insert
50: template<class ItemType>
51: bool LinkedList<ItemType>::remove(int position)
52: {
53: bool ableToRemove = (position >= 1) && (position <= itemCount);
54: if (ableToRemove)
55: {
56: Node<ItemType>* curPtr = nullptr;
57: if (position == 1)
58: {
59: // Remove the first node in the chain
60: curPtr = headPtr; // Save pointer to node
61: headPtr = headPtr->getNext();
62: }
63: else
64: {
65: // Find node that is before the one to delete
66: Node<ItemType>* prevPtr = getNodeAt(position - 1);
67:
68: // Point to node to delete
69: curPtr = prevPtr->getNext();
70:
71: // Disconnect indicated node from chain by connecting the
72: // prior node with the one after
73: prevPtr->setNext(curPtr->getNext());
74: } // end if
75:
76: // Return node to system
77: curPtr->setNext(nullptr);
78: delete curPtr;
79: curPtr = nullptr;
80:
81: itemCount--; // Decrease count of entries
82: } // end if
83:
84: return ableToRemove;
85: } // end remove
87: template<class ItemType>
88: void LinkedList<ItemType>::clear()
89: {
90: while (!isEmpty())
91: remove(1);
92: } // end clear
94: template<class ItemType>
95: ItemType LinkedList<ItemType>::getEntry(int position) const throw(PrecondViolatedExcep)
96: {
97: // Enforce precondition
98: bool ableToGet = (position >= 1) && (position <= itemCount);
99: if (ableToGet)
100: {
101: Node<ItemType>* nodePtr = getNodeAt(position);
102: return nodePtr->getItem();
103: }
104: else
105: {
106: string message = "getEntry() called with an empty list or ";
107: message = message + "invalid position.";
108: throw(PrecondViolatedExcep(message));
109: } // end if
110: } // end getEntry
112: template<class ItemType>
113: Node<ItemType>* LinkedList<ItemType>::getNodeAt(int position) const
114: {
115: // Debugging check of precondition
116: assert( (position >= 1) && (position <= itemCount) );
117:
118: // Count from the beginning of the chain
119: Node<ItemType>* curPtr = headPtr;
120: for (int skip = 1; skip < position; skip++)
121: curPtr = curPtr->getNext();
122:
123: return curPtr;
124: } // end getNodeAt
126: // RECURSIVE
127: template<class ItemType>
128: Node<ItemType>* LinkedList<ItemType>::insertNode(int position, Node<ItemType>* newNodePtr,
129: Node<ItemType>* subChainPtr)
130: {
131: if (position == 1)
132: {
133: // Insert new node at beginning of subchain
134: newNodePtr->setNext(subChainPtr);
135: subChainPtr = newNodePtr;
136: itemCount++; // Increase count of entries
137: }
138: else
139: {
140: Node<ItemType>* afterPtr = insertNode(position - 1, newNodePtr, subChainPtr->getNext());
141: subChainPtr->setNext(afterPtr);
142: } // end if
143:
144: return subChainPtr;
145: } // end insertNode
147: // End of implementation file.