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.

Information

Dependencies not included with library:

#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");
}

Files at this revision

API Documentation at this revision

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

LL.cpp Show annotated file Show diff for this revision Revisions of this file
LL.h Show annotated file Show diff for this revision Revisions of this file
LinkedList.cpp Show diff for this revision Revisions of this file
LinkedList.h Show diff for this revision Revisions of this file
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_ */