1 files changed, 87 insertions, 0 deletions

diff --git a/src/linkedlist.h b/src/linkedlist.h
new file mode 100644
index 0000000..c45cc9b
--- /dev/null
+++ b/src/linkedlist.h
@@ -0,0 +1,87 @@
+/**@file
+ * Describes the LinkedList implementation of the List ADT.
+ *@author Mike Buland
+ */
+
+#ifndef LINKEDLIST_H
+#define LINKEDLIST_H
+
+#include <stdio.h>
+#include "list.h"
+
+/** A linked-item implementation of the List ADT.  Since the data is linked
+  * sequentially this is a great choice for lists that will grow and shrink
+  * a lot, but don't require as much random access.  This implementation
+  * includes optomizations that make iterating through data, and appending
+  * items to the list take O(1) time.
+  *@author Mike Buland
+  */
+class LinkedList : public List
+{
+public:
+        /**
+         * Construct a blank LinkedList.
+         */
+    LinkedList();
+
+        /**
+         * Delete all list data, but do not delete any of the contained elements.
+         */
+    ~LinkedList();
+
+    void *getAt( int nIndex );
+    void append( void *pData );
+    void insertBefore( void *pData, int nPos = 0 );
+    int getSize(  );
+    bool isEmpty(  );
+        void deleteAt( int nIndex );
+        void empty();
+        void setSize( int nNewSize );
+        void setAt( int nIndex, void *pData );
+
+private:
+        /**
+         * A link in the linked list.
+         */
+    class Link
+    {
+      public:
+                /**
+                 * Construct an empty link.
+                 */
+        Link()
+        {
+            pData = NULL;
+            pNext = NULL;
+        }
+                /**
+                 * Construct a link filled in with useful data.
+                 *@param newData The data this link should hold.
+                 *@param newNext The next link that this link should point to.
+                 */
+        Link( void *newData = NULL, Link * newNext = NULL )
+        {
+            pData = newData;
+            pNext = newNext;
+        }
+        void *pData;    /**< A pointer to the contained data. */
+        Link *pNext;    /**< A pointer to the next link in the chain */
+    };
+
+        /**
+         * Finds a pointer to the link at index index.  This is the core function
+         * called for all seek operations, and has been optimized as heavily as
+         * possible.
+         *@param index The zero-based index of the desired element.
+         *@returns A pointer to the requested Link, or NULL if it isn't found.
+         */
+        Link *getPtrTo( int index );
+    Link *pBase;        /**< The first link in the list. */
+        Link *pTop;             /**< The Last link in the list. */
+    Link *pLast;        /**< The previously requested link. */
+    int nSize;          /**< The number of contained links. */
+    int nLast;          /**< The index of the previously requested link. */
+};
+
+#endif
+