Sam Grove
Class to manage a linked list. Utility that can be built on or used alone
Dependents: Waldo_Embed_V2 elevator_with_queue RaheeNew DS1820 ... more
Good information on linked list basics here.
#include "mbed.h"
#include "LL.h"
LL<node>list;
int main()
{
node *tmp;
list.push((char *)"Two\n");
list.append((char *)"Three\n");
list.append((char *)"Four\n");
list.push((char*)"One\n");
list.append((char*)"Five\n");
for(int i=1; i<=list.length(); i++)
{
tmp = list.pop(i);
printf("%s", (char *)tmp->data );
}
error("done\n");
}
Revision 8:a7956e9c2bf5, committed 2019-12-28
- Comitter:
- sam_grove
- Date:
- Sat Dec 28 19:06:07 2019 +0000
- Parent:
- 7:4ed66162aaa8
- Commit message:
- mbed-os has files and a class named LinkedList. Rename the file and class name to match the files.
Changed in this revision
diff -r 4ed66162aaa8 -r a7956e9c2bf5 LL.cpp
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/LL.cpp Sat Dec 28 19:06:07 2019 +0000
@@ -0,0 +1,179 @@
+/**
+ * @file LL.cpp
+ * @brief Core Utility - Templated Linked List class
+ * @author sam grove
+ * @version 1.0
+ * @see
+ *
+ * Copyright (c) 2013
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#include "LL.h" // api wrapper
+
+template<class retT>
+LL<retT>::LL()
+{
+ // clear the member
+ _head = 0;
+
+ return;
+}
+
+template<class retT>
+LL<retT>::~LL()
+{
+ // free any memory that is on the heap
+ while(remove(1) != NULL);
+
+ return;
+}
+
+template<class retT>
+retT *LL<retT>::push(void *data)
+{
+ retT *new_node = new retT [1];
+ // update the next item in the list to the current head
+ new_node->next = _head;
+ // store the address to the linked datatype
+ new_node->data = data;
+ _head = new_node;
+
+ return _head;
+}
+
+//template<class retT>
+//retT *LL<retT>::insert(void *data, uint32_t loc)
+//{
+// retT *new_node = new retT [1];
+// retT *current = _head->next;
+// retT *prev = _head;
+// // move to the item we want to insert
+// for (uint32_t i=1; i!=(loc-1); i++)
+// {
+// prev = current;
+// current = current->next;
+// }
+// // store the address to the linked datatype
+// new_node->data = data;
+// // clear the next pointer
+// new_node->next = 0;
+// // update the list and store the new stuff
+// prev->next = new_node;
+// new_node->next = current;
+// // store the address to the linked datatype
+// _head->data = data;
+//
+// return prev->next;
+//}
+
+template<class retT>
+retT *LL<retT>::append(void *data)
+{
+ retT *current = _head;
+ retT *new_node = new retT [1];
+ // store the address to the linked datatype
+ new_node->data = data;
+ // clear the next pointer
+ new_node->next = 0;
+ // check for an empty list
+ if (0 == current)
+ {
+ _head = new_node;
+ return _head;
+ }
+ else
+ {
+ // look for the end of the list
+ while (current->next != 0)
+ {
+ current = current->next;
+ }
+ // and then add the new item to the list
+ current->next = new_node;
+ }
+
+ return current->next;
+}
+
+template<class retT>
+retT *LL<retT>::remove(uint32_t loc)
+{
+ retT *current = _head;
+ retT *prev = 0;
+ // make sure we have an item to remove
+ if ((loc <= length()) && (loc > 0))
+ {
+ // move to the item we want to delete
+ if (1 == loc)
+ {
+ _head = current->next;
+ delete [] current;
+ }
+ else
+ {
+ for (uint32_t i=2; i<=loc; ++i)
+ {
+ prev = current;
+ current = current->next;
+ }
+ // store the item + 1 to replace what we are deleting
+ prev->next = current->next;
+ delete [] current;
+ }
+ }
+
+ return _head;
+}
+
+template<class retT>
+retT *LL<retT>::pop(uint32_t loc)
+{
+ retT *current = _head;
+ // make sure we have something in the location
+ if ((loc > length()) || (loc == 0))
+ {
+ return 0;
+ }
+ // and if so jump down the list
+ for (uint32_t i=2; i<=loc; ++i)
+ {
+ current = current->next;
+ }
+
+ return current;
+}
+
+template<class retT>
+uint32_t LL<retT>::length(void)
+{
+ int32_t count = 0;
+ retT *current = _head;
+ //loop until the end of the list is found
+ while (current != 0)
+ {
+ ++count;
+ current = current->next;
+ }
+
+ return count;
+}
+
+// pre-define the type for the linker
+template class LL<node>;
+
+
+
+
+
diff -r 4ed66162aaa8 -r a7956e9c2bf5 LL.h
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/LL.h Sat Dec 28 19:06:07 2019 +0000
@@ -0,0 +1,124 @@
+/**
+ * @file LL.h
+ * @brief Core Utility - Templated Linked List class
+ * @author sam grove
+ * @version 1.0
+ * @see
+ *
+ * Copyright (c) 2013
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#ifndef LL_H_
+#define LL_H_
+
+#include <stdint.h>
+#include <cstddef>
+
+/**
+ * @struct node
+ * @brief The Linked List structure
+ */
+struct node
+{
+ void *data; /*!< pointer to list member data */
+ struct node *next; /*!< pointer to the next list member */
+};
+
+/** Example using the LL Class
+ * @code
+ * #include "mbed.h"
+ * #include "LL.h"
+ *
+ * LL<node>list;
+ *
+ * int main()
+ * {
+ * node *tmp;
+ *
+ * list.push((char *)"Two\n");
+ * list.append((char *)"Three\n");
+ * list.append((char *)"Four\n");
+ * list.push((char*)"One\n");
+ * list.append((char*)"Five\n");
+ *
+ * for(int i=1; i<=list.length(); i++)
+ * {
+ * tmp = list.pop(i);
+ * printf("%s", (char *)tmp->data);
+ * }
+ *
+ * error("done\n");
+ * }
+ * @endcode
+ */
+
+/**
+ * @class LL
+ * @brief API abstraction for a Linked List
+ */
+template<class retT>
+class LL
+{
+protected:
+ retT *_head;
+
+public:
+ /** Create the LL object
+ */
+ LL();
+
+ /** Deconstructor for the LL object
+ * Removes any members
+ */
+ ~LL();
+
+ /** Add a member to the begining of the list
+ * @param data - Some data type that is added to the list
+ * @return The member that was just inserted (NULL if empty)
+ */
+ retT *push(void *data);
+
+// /** Add a member to some position in the list
+// * @param data - Some data type that is added to the list
+// * @param loc - Place in the list to put the data
+// * @return The member that was just inserted (NULL if empty)
+// */
+// retT *insert(void *data, uint32_t loc);
+
+ /** Add a member to the end of the list
+ * @param data - Some data type that is added to the list
+ * @return The member that was just inserted (NULL if empty)
+ */
+ retT *append(void *data);
+
+ /** Remove a member from the list
+ * @param loc - The location of the member to remove
+ * @return The head of the list
+ */
+ retT *remove(uint32_t loc);
+
+ /** Get access to a member from the list
+ * @param loc - The location of the member to access
+ * @return The member that was just requested (NULL if empty or out of bounds)
+ */
+ retT *pop(uint32_t loc);
+
+ /** Get the length of the list
+ * @return The number of members in the list
+ */
+ uint32_t length(void);
+};
+
+#endif /* LINKEDLIST_H_ */
diff -r 4ed66162aaa8 -r a7956e9c2bf5 LinkedList.cpp
--- a/LinkedList.cpp Sun Feb 23 14:09:48 2014 +0000
+++ /dev/null Thu Jan 01 00:00:00 1970 +0000
@@ -1,194 +0,0 @@
-/**
- * @file LinkedList.cpp
- * @brief Core Utility - Templated Linked List class
- * @author sam grove
- * @version 1.0
- * @see
- *
- * Copyright (c) 2013
- *
- * Licensed under the Apache License, Version 2.0 (the "License");
- * you may not use this file except in compliance with the License.
- * You may obtain a copy of the License at
- *
- * http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing, software
- * distributed under the License is distributed on an "AS IS" BASIS,
- * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- * See the License for the specific language governing permissions and
- * limitations under the License.
- */
-
-#include "LinkedList.h" // api wrapper
-
-template<class retT>
-LinkedList<retT>::LinkedList()
-{
- // clear the member
- _head = 0;
-
- return;
-}
-
-template<class retT>
-LinkedList<retT>::~LinkedList()
-{
- // free any memory that is on the heap
- while(remove(1) != NULL);
-
- return;
-}
-
-template<class retT>
-retT *LinkedList<retT>::push(void *data)
-{
- retT *new_node = new retT [1];
- // make sure the new object was allocated
- if (0 == new_node)
- {
- error("Memory allocation failed\n");
- }
- // update the next item in the list to the current head
- new_node->next = _head;
- // store the address to the linked datatype
- new_node->data = data;
- _head = new_node;
-
- return _head;
-}
-
-//template<class retT>
-//retT *LinkedList<retT>::insert(void *data, uint32_t loc)
-//{
-// retT *new_node = new retT [1];
-// // make sure the new object was allocated
-// if (0 == new_node)
-// {
-// error("Memory allocation failed\n");
-// }
-// retT *current = _head->next;
-// retT *prev = _head;
-// // move to the item we want to insert
-// for (uint32_t i=1; i!=(loc-1); i++)
-// {
-// prev = current;
-// current = current->next;
-// }
-// // store the address to the linked datatype
-// new_node->data = data;
-// // clear the next pointer
-// new_node->next = 0;
-// // update the list and store the new stuff
-// prev->next = new_node;
-// new_node->next = current;
-// // store the address to the linked datatype
-// _head->data = data;
-//
-// return prev->next;
-//}
-
-template<class retT>
-retT *LinkedList<retT>::append(void *data)
-{
- retT *current = _head;
- retT *new_node = new retT [1];
- // make sure the new object was allocated
- if (0 == new_node)
- {
- error("Memory allocation failed\n");
- }
- // store the address to the linked datatype
- new_node->data = data;
- // clear the next pointer
- new_node->next = 0;
- // check for an empty list
- if (0 == current)
- {
- _head = new_node;
- return _head;
- }
- else
- {
- // look for the end of the list
- while (current->next != 0)
- {
- current = current->next;
- }
- // and then add the new item to the list
- current->next = new_node;
- }
-
- return current->next;
-}
-
-template<class retT>
-retT *LinkedList<retT>::remove(uint32_t loc)
-{
- retT *current = _head;
- retT *prev = 0;
- // make sure we have an item to remove
- if ((loc <= length()) && (loc > 0))
- {
- // move to the item we want to delete
- if (1 == loc)
- {
- _head = current->next;
- delete [] current;
- }
- else
- {
- for (uint32_t i=2; i<=loc; ++i)
- {
- prev = current;
- current = current->next;
- }
- // store the item + 1 to replace what we are deleting
- prev->next = current->next;
- delete [] current;
- }
- }
-
- return _head;
-}
-
-template<class retT>
-retT *LinkedList<retT>::pop(uint32_t loc)
-{
- retT *current = _head;
- // make sure we have something in the location
- if ((loc > length()) || (loc == 0))
- {
- return 0;
- }
- // and if so jump down the list
- for (uint32_t i=2; i<=loc; ++i)
- {
- current = current->next;
- }
-
- return current;
-}
-
-template<class retT>
-uint32_t LinkedList<retT>::length(void)
-{
- int32_t count = 0;
- retT *current = _head;
- //loop until the end of the list is found
- while (current != 0)
- {
- ++count;
- current = current->next;
- }
-
- return count;
-}
-
-// pre-define the type for the linker
-template class LinkedList<node>;
-
-
-
-
-
diff -r 4ed66162aaa8 -r a7956e9c2bf5 LinkedList.h
--- a/LinkedList.h Sun Feb 23 14:09:48 2014 +0000
+++ /dev/null Thu Jan 01 00:00:00 1970 +0000
@@ -1,124 +0,0 @@
-/**
- * @file LinkedList.h
- * @brief Core Utility - Templated Linked List class
- * @author sam grove
- * @version 1.0
- * @see
- *
- * Copyright (c) 2013
- *
- * Licensed under the Apache License, Version 2.0 (the "License");
- * you may not use this file except in compliance with the License.
- * You may obtain a copy of the License at
- *
- * http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing, software
- * distributed under the License is distributed on an "AS IS" BASIS,
- * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- * See the License for the specific language governing permissions and
- * limitations under the License.
- */
-
-#ifndef LINKEDLIST_H_
-#define LINKEDLIST_H_
-
-#include <stdint.h>
-#include "mbed.h"
-
-/**
- * @struct node
- * @brief The Linked List structure
- */
-struct node
-{
- void *data; /*!< pointer to list member data */
- struct node *next; /*!< pointer to the next list member */
-};
-
-/** Example using the LinkedList Class
- * @code
- * #include "mbed.h"
- * #include "LinkedList.h"
- *
- * LinkedList<node>list;
- *
- * int main()
- * {
- * node *tmp;
- *
- * list.push((char *)"Two\n");
- * list.append((char *)"Three\n");
- * list.append((char *)"Four\n");
- * list.push((char*)"One\n");
- * list.append((char*)"Five\n");
- *
- * for(int i=1; i<=list.length(); i++)
- * {
- * tmp = list.pop(i);
- * printf("%s", (char *)tmp->data);
- * }
- *
- * error("done\n");
- * }
- * @endcode
- */
-
-/**
- * @class LinkedList
- * @brief API abstraction for a Linked List
- */
-template<class retT>
-class LinkedList
-{
-protected:
- retT *_head;
-
-public:
- /** Create the LinkedList object
- */
- LinkedList();
-
- /** Deconstructor for the LinkedList object
- * Removes any members
- */
- ~LinkedList();
-
- /** Add a member to the begining of the list
- * @param data - Some data type that is added to the list
- * @return The member that was just inserted (NULL if empty)
- */
- retT *push(void *data);
-
-// /** Add a member to some position in the list
-// * @param data - Some data type that is added to the list
-// * @param loc - Place in the list to put the data
-// * @return The member that was just inserted (NULL if empty)
-// */
-// retT *insert(void *data, uint32_t loc);
-
- /** Add a member to the end of the list
- * @param data - Some data type that is added to the list
- * @return The member that was just inserted (NULL if empty)
- */
- retT *append(void *data);
-
- /** Remove a member from the list
- * @param loc - The location of the member to remove
- * @return The head of the list
- */
- retT *remove(uint32_t loc);
-
- /** Get access to a member from the list
- * @param loc - The location of the member to access
- * @return The member that was just requested (NULL if empty or out of bounds)
- */
- retT *pop(uint32_t loc);
-
- /** Get the length of the list
- * @return The number of members in the list
- */
- uint32_t length(void);
-};
-
-#endif /* LINKEDLIST_H_ */