Sam Grove / LinkedList

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

LinkedList.cpp@5:28e11c75b433, 2013-05-13 (annotated)

Committer:
sam_grove
Date:
Mon May 13 04:38:05 2013 +0000
Revision:
5:28e11c75b433
Parent:
4:59b2aa82b517
Child:
6:e3ab7684c395
Fixed bug in remove member. Deconstructor was hanging due to logic problem when looping to clear the list (last member)

Who changed what in which revision?

UserRevisionLine numberNew contents of line
sam_grove 0:3f64a15357ac 1 /**
sam_grove 0:3f64a15357ac 2 * @file LinkedList.cpp
sam_grove 0:3f64a15357ac 3 * @brief Core Utility - Templated Linked List class
sam_grove 0:3f64a15357ac 4 * @author sam grove
sam_grove 0:3f64a15357ac 5 * @version 1.0
sam_grove 0:3f64a15357ac 6 * @see
sam_grove 0:3f64a15357ac 7 *
sam_grove 0:3f64a15357ac 8 * Copyright (c) 2013
sam_grove 0:3f64a15357ac 9 *
sam_grove 0:3f64a15357ac 10 * Licensed under the Apache License, Version 2.0 (the "License");
sam_grove 0:3f64a15357ac 11 * you may not use this file except in compliance with the License.
sam_grove 0:3f64a15357ac 12 * You may obtain a copy of the License at
sam_grove 0:3f64a15357ac 13 *
sam_grove 0:3f64a15357ac 14 * http://www.apache.org/licenses/LICENSE-2.0
sam_grove 0:3f64a15357ac 15 *
sam_grove 0:3f64a15357ac 16 * Unless required by applicable law or agreed to in writing, software
sam_grove 0:3f64a15357ac 17 * distributed under the License is distributed on an "AS IS" BASIS,
sam_grove 0:3f64a15357ac 18 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
sam_grove 0:3f64a15357ac 19 * See the License for the specific language governing permissions and
sam_grove 0:3f64a15357ac 20 * limitations under the License.
sam_grove 0:3f64a15357ac 21 */
sam_grove 0:3f64a15357ac 22
sam_grove 0:3f64a15357ac 23 #include "LinkedList.h" // api wrapper
sam_grove 1:a032c0392ba1 24 #include "LogUtil.h"
sam_grove 0:3f64a15357ac 25
sam_grove 0:3f64a15357ac 26 template<class retT>
sam_grove 0:3f64a15357ac 27 LinkedList<retT>::LinkedList()
sam_grove 0:3f64a15357ac 28 {
sam_grove 4:59b2aa82b517 29 // clear the member
sam_grove 0:3f64a15357ac 30 _head = 0;
sam_grove 4:59b2aa82b517 31 // _head->next = 0;
sam_grove 0:3f64a15357ac 32
sam_grove 0:3f64a15357ac 33 return;
sam_grove 0:3f64a15357ac 34 }
sam_grove 0:3f64a15357ac 35
sam_grove 0:3f64a15357ac 36 template<class retT>
sam_grove 0:3f64a15357ac 37 LinkedList<retT>::~LinkedList()
sam_grove 0:3f64a15357ac 38 {
sam_grove 0:3f64a15357ac 39 // free any memory that is on the heap
sam_grove 5:28e11c75b433 40 while(remove(1) != NULL);
sam_grove 0:3f64a15357ac 41
sam_grove 0:3f64a15357ac 42 return;
sam_grove 0:3f64a15357ac 43 }
sam_grove 0:3f64a15357ac 44
sam_grove 0:3f64a15357ac 45 template<class retT>
sam_grove 0:3f64a15357ac 46 retT *LinkedList<retT>::push(void *data)
sam_grove 0:3f64a15357ac 47 {
sam_grove 0:3f64a15357ac 48 retT *new_node = new retT [1];
sam_grove 0:3f64a15357ac 49 // make sure the new object was allocated
sam_grove 0:3f64a15357ac 50 if (0 == new_node)
sam_grove 0:3f64a15357ac 51 {
sam_grove 1:a032c0392ba1 52 ERROR("Memory allocation failed\n");
sam_grove 0:3f64a15357ac 53 }
sam_grove 0:3f64a15357ac 54 // update the next item in the list to the current head
sam_grove 0:3f64a15357ac 55 new_node->next = _head;
sam_grove 0:3f64a15357ac 56 // store the address to the linked datatype
sam_grove 0:3f64a15357ac 57 new_node->data = data;
sam_grove 0:3f64a15357ac 58 _head = new_node;
sam_grove 0:3f64a15357ac 59
sam_grove 0:3f64a15357ac 60 return _head;
sam_grove 0:3f64a15357ac 61 }
sam_grove 0:3f64a15357ac 62
sam_grove 1:a032c0392ba1 63 //template<class retT>
sam_grove 1:a032c0392ba1 64 //retT *LinkedList<retT>::insert(void *data, uint32_t loc)
sam_grove 1:a032c0392ba1 65 //{
sam_grove 1:a032c0392ba1 66 // retT *new_node = new retT [1];
sam_grove 1:a032c0392ba1 67 // // make sure the new object was allocated
sam_grove 1:a032c0392ba1 68 // if (0 == new_node)
sam_grove 1:a032c0392ba1 69 // {
sam_grove 1:a032c0392ba1 70 // ERROR("Memory allocation failed\n");
sam_grove 1:a032c0392ba1 71 // }
sam_grove 1:a032c0392ba1 72 // retT *current = _head->next;
sam_grove 1:a032c0392ba1 73 // retT *prev = _head;
sam_grove 1:a032c0392ba1 74 // // move to the item we want to insert
sam_grove 1:a032c0392ba1 75 // for (uint32_t i=1; i!=(loc-1); i++)
sam_grove 1:a032c0392ba1 76 // {
sam_grove 1:a032c0392ba1 77 // prev = current;
sam_grove 1:a032c0392ba1 78 // current = current->next;
sam_grove 1:a032c0392ba1 79 // }
sam_grove 1:a032c0392ba1 80 // // store the address to the linked datatype
sam_grove 1:a032c0392ba1 81 // new_node->data = data;
sam_grove 1:a032c0392ba1 82 // // clear the next pointer
sam_grove 1:a032c0392ba1 83 // new_node->next = 0;
sam_grove 1:a032c0392ba1 84 // // update the list and store the new stuff
sam_grove 1:a032c0392ba1 85 // prev->next = new_node;
sam_grove 1:a032c0392ba1 86 // new_node->next = current;
sam_grove 1:a032c0392ba1 87 // // store the address to the linked datatype
sam_grove 1:a032c0392ba1 88 // _head->data = data;
sam_grove 1:a032c0392ba1 89 //
sam_grove 1:a032c0392ba1 90 // return prev->next;
sam_grove 1:a032c0392ba1 91 //}
sam_grove 0:3f64a15357ac 92
sam_grove 0:3f64a15357ac 93 template<class retT>
sam_grove 0:3f64a15357ac 94 retT *LinkedList<retT>::append(void *data)
sam_grove 0:3f64a15357ac 95 {
sam_grove 0:3f64a15357ac 96 retT *current = _head;
sam_grove 0:3f64a15357ac 97 retT *new_node = new retT [1];
sam_grove 0:3f64a15357ac 98 // make sure the new object was allocated
sam_grove 0:3f64a15357ac 99 if (0 == new_node)
sam_grove 0:3f64a15357ac 100 {
sam_grove 1:a032c0392ba1 101 ERROR("Memory allocation failed\n");
sam_grove 0:3f64a15357ac 102 }
sam_grove 0:3f64a15357ac 103 // store the address to the linked datatype
sam_grove 0:3f64a15357ac 104 new_node->data = data;
sam_grove 0:3f64a15357ac 105 // clear the next pointer
sam_grove 0:3f64a15357ac 106 new_node->next = 0;
sam_grove 0:3f64a15357ac 107 // check for an empty list
sam_grove 0:3f64a15357ac 108 if (0 == current)
sam_grove 0:3f64a15357ac 109 {
sam_grove 0:3f64a15357ac 110 _head = new_node;
sam_grove 0:3f64a15357ac 111 return _head;
sam_grove 0:3f64a15357ac 112 }
sam_grove 0:3f64a15357ac 113 else
sam_grove 0:3f64a15357ac 114 {
sam_grove 0:3f64a15357ac 115 // look for the end of the list
sam_grove 0:3f64a15357ac 116 while (current->next != 0)
sam_grove 0:3f64a15357ac 117 {
sam_grove 0:3f64a15357ac 118 current = current->next;
sam_grove 0:3f64a15357ac 119 }
sam_grove 0:3f64a15357ac 120 // and then add the new item to the list
sam_grove 0:3f64a15357ac 121 current->next = new_node;
sam_grove 0:3f64a15357ac 122 }
sam_grove 0:3f64a15357ac 123
sam_grove 0:3f64a15357ac 124 return current->next;
sam_grove 0:3f64a15357ac 125 }
sam_grove 0:3f64a15357ac 126
sam_grove 0:3f64a15357ac 127 template<class retT>
sam_grove 0:3f64a15357ac 128 retT *LinkedList<retT>::remove(uint32_t loc)
sam_grove 0:3f64a15357ac 129 {
sam_grove 0:3f64a15357ac 130 retT *current = _head;
sam_grove 1:a032c0392ba1 131 retT *prev = 0;
sam_grove 0:3f64a15357ac 132 // make sure we have an item to remove
sam_grove 5:28e11c75b433 133 if ((loc <= length()) && (loc > 0))
sam_grove 0:3f64a15357ac 134 {
sam_grove 0:3f64a15357ac 135 // move to the item we want to delete
sam_grove 3:c14e7a918e21 136 if (1 == loc)
sam_grove 0:3f64a15357ac 137 {
sam_grove 0:3f64a15357ac 138 _head = current->next;
sam_grove 0:3f64a15357ac 139 delete [] current;
sam_grove 0:3f64a15357ac 140 }
sam_grove 0:3f64a15357ac 141 else
sam_grove 0:3f64a15357ac 142 {
sam_grove 3:c14e7a918e21 143 for (uint32_t i=2; i<=loc; ++i)
sam_grove 0:3f64a15357ac 144 {
sam_grove 0:3f64a15357ac 145 prev = current;
sam_grove 0:3f64a15357ac 146 current = current->next;
sam_grove 0:3f64a15357ac 147 }
sam_grove 0:3f64a15357ac 148 // store the item + 1 to replace what we are deleting
sam_grove 0:3f64a15357ac 149 prev->next = current->next;
sam_grove 0:3f64a15357ac 150 delete [] current;
sam_grove 0:3f64a15357ac 151 }
sam_grove 0:3f64a15357ac 152 }
sam_grove 0:3f64a15357ac 153
sam_grove 0:3f64a15357ac 154 return _head;
sam_grove 0:3f64a15357ac 155 }
sam_grove 0:3f64a15357ac 156
sam_grove 0:3f64a15357ac 157 template<class retT>
sam_grove 0:3f64a15357ac 158 retT *LinkedList<retT>::pop(uint32_t loc)
sam_grove 0:3f64a15357ac 159 {
sam_grove 0:3f64a15357ac 160 retT *current = _head;
sam_grove 0:3f64a15357ac 161 // make sure we have something in the location
sam_grove 3:c14e7a918e21 162 if ((loc > length()) || (loc == 0))
sam_grove 0:3f64a15357ac 163 {
sam_grove 0:3f64a15357ac 164 return 0;
sam_grove 0:3f64a15357ac 165 }
sam_grove 0:3f64a15357ac 166 // and if so jump down the list
sam_grove 3:c14e7a918e21 167 for (uint32_t i=2; i<=loc; ++i)
sam_grove 0:3f64a15357ac 168 {
sam_grove 0:3f64a15357ac 169 current = current->next;
sam_grove 0:3f64a15357ac 170 }
sam_grove 0:3f64a15357ac 171
sam_grove 0:3f64a15357ac 172 return current;
sam_grove 0:3f64a15357ac 173 }
sam_grove 0:3f64a15357ac 174
sam_grove 0:3f64a15357ac 175 template<class retT>
sam_grove 0:3f64a15357ac 176 uint32_t LinkedList<retT>::length(void)
sam_grove 0:3f64a15357ac 177 {
sam_grove 3:c14e7a918e21 178 int32_t count = 0;
sam_grove 0:3f64a15357ac 179 retT *current = _head;
sam_grove 0:3f64a15357ac 180 //loop until the end of the list is found
sam_grove 0:3f64a15357ac 181 while (current != 0)
sam_grove 0:3f64a15357ac 182 {
sam_grove 3:c14e7a918e21 183 ++count;
sam_grove 0:3f64a15357ac 184 current = current->next;
sam_grove 0:3f64a15357ac 185 }
sam_grove 0:3f64a15357ac 186
sam_grove 0:3f64a15357ac 187 return count;
sam_grove 0:3f64a15357ac 188 }
sam_grove 0:3f64a15357ac 189
sam_grove 1:a032c0392ba1 190 // pre-define the type for the linker
sam_grove 0:3f64a15357ac 191 template class LinkedList<node>;
sam_grove 0:3f64a15357ac 192
sam_grove 0:3f64a15357ac 193
sam_grove 0:3f64a15357ac 194
sam_grove 0:3f64a15357ac 195
sam_grove 0:3f64a15357ac 196