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"); }
LinkedList.cpp@7:4ed66162aaa8, 2014-02-23 (annotated)
- Committer:
- Sissors
- Date:
- Sun Feb 23 14:09:48 2014 +0000
- Revision:
- 7:4ed66162aaa8
- Parent:
- 6:e3ab7684c395
Removed LogUtil dependency
Who changed what in which revision?
User | Revision | Line number | New 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 | 0:3f64a15357ac | 24 | |
sam_grove | 0:3f64a15357ac | 25 | template<class retT> |
sam_grove | 0:3f64a15357ac | 26 | LinkedList<retT>::LinkedList() |
sam_grove | 0:3f64a15357ac | 27 | { |
sam_grove | 4:59b2aa82b517 | 28 | // clear the member |
sam_grove | 0:3f64a15357ac | 29 | _head = 0; |
sam_grove | 0:3f64a15357ac | 30 | |
sam_grove | 0:3f64a15357ac | 31 | return; |
sam_grove | 0:3f64a15357ac | 32 | } |
sam_grove | 0:3f64a15357ac | 33 | |
sam_grove | 0:3f64a15357ac | 34 | template<class retT> |
sam_grove | 0:3f64a15357ac | 35 | LinkedList<retT>::~LinkedList() |
sam_grove | 0:3f64a15357ac | 36 | { |
sam_grove | 0:3f64a15357ac | 37 | // free any memory that is on the heap |
sam_grove | 5:28e11c75b433 | 38 | while(remove(1) != NULL); |
sam_grove | 0:3f64a15357ac | 39 | |
sam_grove | 0:3f64a15357ac | 40 | return; |
sam_grove | 0:3f64a15357ac | 41 | } |
sam_grove | 0:3f64a15357ac | 42 | |
sam_grove | 0:3f64a15357ac | 43 | template<class retT> |
sam_grove | 0:3f64a15357ac | 44 | retT *LinkedList<retT>::push(void *data) |
sam_grove | 0:3f64a15357ac | 45 | { |
sam_grove | 0:3f64a15357ac | 46 | retT *new_node = new retT [1]; |
sam_grove | 0:3f64a15357ac | 47 | // make sure the new object was allocated |
sam_grove | 0:3f64a15357ac | 48 | if (0 == new_node) |
sam_grove | 0:3f64a15357ac | 49 | { |
Sissors | 7:4ed66162aaa8 | 50 | error("Memory allocation failed\n"); |
sam_grove | 0:3f64a15357ac | 51 | } |
sam_grove | 0:3f64a15357ac | 52 | // update the next item in the list to the current head |
sam_grove | 0:3f64a15357ac | 53 | new_node->next = _head; |
sam_grove | 0:3f64a15357ac | 54 | // store the address to the linked datatype |
sam_grove | 0:3f64a15357ac | 55 | new_node->data = data; |
sam_grove | 0:3f64a15357ac | 56 | _head = new_node; |
sam_grove | 0:3f64a15357ac | 57 | |
sam_grove | 0:3f64a15357ac | 58 | return _head; |
sam_grove | 0:3f64a15357ac | 59 | } |
sam_grove | 0:3f64a15357ac | 60 | |
sam_grove | 1:a032c0392ba1 | 61 | //template<class retT> |
sam_grove | 1:a032c0392ba1 | 62 | //retT *LinkedList<retT>::insert(void *data, uint32_t loc) |
sam_grove | 1:a032c0392ba1 | 63 | //{ |
sam_grove | 1:a032c0392ba1 | 64 | // retT *new_node = new retT [1]; |
sam_grove | 1:a032c0392ba1 | 65 | // // make sure the new object was allocated |
sam_grove | 1:a032c0392ba1 | 66 | // if (0 == new_node) |
sam_grove | 1:a032c0392ba1 | 67 | // { |
Sissors | 7:4ed66162aaa8 | 68 | // error("Memory allocation failed\n"); |
sam_grove | 1:a032c0392ba1 | 69 | // } |
sam_grove | 1:a032c0392ba1 | 70 | // retT *current = _head->next; |
sam_grove | 1:a032c0392ba1 | 71 | // retT *prev = _head; |
sam_grove | 1:a032c0392ba1 | 72 | // // move to the item we want to insert |
sam_grove | 1:a032c0392ba1 | 73 | // for (uint32_t i=1; i!=(loc-1); i++) |
sam_grove | 1:a032c0392ba1 | 74 | // { |
sam_grove | 1:a032c0392ba1 | 75 | // prev = current; |
sam_grove | 1:a032c0392ba1 | 76 | // current = current->next; |
sam_grove | 1:a032c0392ba1 | 77 | // } |
sam_grove | 1:a032c0392ba1 | 78 | // // store the address to the linked datatype |
sam_grove | 1:a032c0392ba1 | 79 | // new_node->data = data; |
sam_grove | 1:a032c0392ba1 | 80 | // // clear the next pointer |
sam_grove | 1:a032c0392ba1 | 81 | // new_node->next = 0; |
sam_grove | 1:a032c0392ba1 | 82 | // // update the list and store the new stuff |
sam_grove | 1:a032c0392ba1 | 83 | // prev->next = new_node; |
sam_grove | 1:a032c0392ba1 | 84 | // new_node->next = current; |
sam_grove | 1:a032c0392ba1 | 85 | // // store the address to the linked datatype |
sam_grove | 1:a032c0392ba1 | 86 | // _head->data = data; |
sam_grove | 1:a032c0392ba1 | 87 | // |
sam_grove | 1:a032c0392ba1 | 88 | // return prev->next; |
sam_grove | 1:a032c0392ba1 | 89 | //} |
sam_grove | 0:3f64a15357ac | 90 | |
sam_grove | 0:3f64a15357ac | 91 | template<class retT> |
sam_grove | 0:3f64a15357ac | 92 | retT *LinkedList<retT>::append(void *data) |
sam_grove | 0:3f64a15357ac | 93 | { |
sam_grove | 0:3f64a15357ac | 94 | retT *current = _head; |
sam_grove | 0:3f64a15357ac | 95 | retT *new_node = new retT [1]; |
sam_grove | 0:3f64a15357ac | 96 | // make sure the new object was allocated |
sam_grove | 0:3f64a15357ac | 97 | if (0 == new_node) |
sam_grove | 0:3f64a15357ac | 98 | { |
Sissors | 7:4ed66162aaa8 | 99 | error("Memory allocation failed\n"); |
sam_grove | 0:3f64a15357ac | 100 | } |
sam_grove | 0:3f64a15357ac | 101 | // store the address to the linked datatype |
sam_grove | 0:3f64a15357ac | 102 | new_node->data = data; |
sam_grove | 0:3f64a15357ac | 103 | // clear the next pointer |
sam_grove | 0:3f64a15357ac | 104 | new_node->next = 0; |
sam_grove | 0:3f64a15357ac | 105 | // check for an empty list |
sam_grove | 0:3f64a15357ac | 106 | if (0 == current) |
sam_grove | 0:3f64a15357ac | 107 | { |
sam_grove | 0:3f64a15357ac | 108 | _head = new_node; |
sam_grove | 0:3f64a15357ac | 109 | return _head; |
sam_grove | 0:3f64a15357ac | 110 | } |
sam_grove | 0:3f64a15357ac | 111 | else |
sam_grove | 0:3f64a15357ac | 112 | { |
sam_grove | 0:3f64a15357ac | 113 | // look for the end of the list |
sam_grove | 0:3f64a15357ac | 114 | while (current->next != 0) |
sam_grove | 0:3f64a15357ac | 115 | { |
sam_grove | 0:3f64a15357ac | 116 | current = current->next; |
sam_grove | 0:3f64a15357ac | 117 | } |
sam_grove | 0:3f64a15357ac | 118 | // and then add the new item to the list |
sam_grove | 0:3f64a15357ac | 119 | current->next = new_node; |
sam_grove | 0:3f64a15357ac | 120 | } |
sam_grove | 0:3f64a15357ac | 121 | |
sam_grove | 0:3f64a15357ac | 122 | return current->next; |
sam_grove | 0:3f64a15357ac | 123 | } |
sam_grove | 0:3f64a15357ac | 124 | |
sam_grove | 0:3f64a15357ac | 125 | template<class retT> |
sam_grove | 0:3f64a15357ac | 126 | retT *LinkedList<retT>::remove(uint32_t loc) |
sam_grove | 0:3f64a15357ac | 127 | { |
sam_grove | 0:3f64a15357ac | 128 | retT *current = _head; |
sam_grove | 1:a032c0392ba1 | 129 | retT *prev = 0; |
sam_grove | 0:3f64a15357ac | 130 | // make sure we have an item to remove |
sam_grove | 5:28e11c75b433 | 131 | if ((loc <= length()) && (loc > 0)) |
sam_grove | 0:3f64a15357ac | 132 | { |
sam_grove | 0:3f64a15357ac | 133 | // move to the item we want to delete |
sam_grove | 3:c14e7a918e21 | 134 | if (1 == loc) |
sam_grove | 0:3f64a15357ac | 135 | { |
sam_grove | 0:3f64a15357ac | 136 | _head = current->next; |
sam_grove | 0:3f64a15357ac | 137 | delete [] current; |
sam_grove | 0:3f64a15357ac | 138 | } |
sam_grove | 0:3f64a15357ac | 139 | else |
sam_grove | 0:3f64a15357ac | 140 | { |
sam_grove | 3:c14e7a918e21 | 141 | for (uint32_t i=2; i<=loc; ++i) |
sam_grove | 0:3f64a15357ac | 142 | { |
sam_grove | 0:3f64a15357ac | 143 | prev = current; |
sam_grove | 0:3f64a15357ac | 144 | current = current->next; |
sam_grove | 0:3f64a15357ac | 145 | } |
sam_grove | 0:3f64a15357ac | 146 | // store the item + 1 to replace what we are deleting |
sam_grove | 0:3f64a15357ac | 147 | prev->next = current->next; |
sam_grove | 0:3f64a15357ac | 148 | delete [] current; |
sam_grove | 0:3f64a15357ac | 149 | } |
sam_grove | 0:3f64a15357ac | 150 | } |
sam_grove | 0:3f64a15357ac | 151 | |
sam_grove | 0:3f64a15357ac | 152 | return _head; |
sam_grove | 0:3f64a15357ac | 153 | } |
sam_grove | 0:3f64a15357ac | 154 | |
sam_grove | 0:3f64a15357ac | 155 | template<class retT> |
sam_grove | 0:3f64a15357ac | 156 | retT *LinkedList<retT>::pop(uint32_t loc) |
sam_grove | 0:3f64a15357ac | 157 | { |
sam_grove | 0:3f64a15357ac | 158 | retT *current = _head; |
sam_grove | 0:3f64a15357ac | 159 | // make sure we have something in the location |
sam_grove | 3:c14e7a918e21 | 160 | if ((loc > length()) || (loc == 0)) |
sam_grove | 0:3f64a15357ac | 161 | { |
sam_grove | 0:3f64a15357ac | 162 | return 0; |
sam_grove | 0:3f64a15357ac | 163 | } |
sam_grove | 0:3f64a15357ac | 164 | // and if so jump down the list |
sam_grove | 3:c14e7a918e21 | 165 | for (uint32_t i=2; i<=loc; ++i) |
sam_grove | 0:3f64a15357ac | 166 | { |
sam_grove | 0:3f64a15357ac | 167 | current = current->next; |
sam_grove | 0:3f64a15357ac | 168 | } |
sam_grove | 0:3f64a15357ac | 169 | |
sam_grove | 0:3f64a15357ac | 170 | return current; |
sam_grove | 0:3f64a15357ac | 171 | } |
sam_grove | 0:3f64a15357ac | 172 | |
sam_grove | 0:3f64a15357ac | 173 | template<class retT> |
sam_grove | 0:3f64a15357ac | 174 | uint32_t LinkedList<retT>::length(void) |
sam_grove | 0:3f64a15357ac | 175 | { |
sam_grove | 3:c14e7a918e21 | 176 | int32_t count = 0; |
sam_grove | 0:3f64a15357ac | 177 | retT *current = _head; |
sam_grove | 0:3f64a15357ac | 178 | //loop until the end of the list is found |
sam_grove | 0:3f64a15357ac | 179 | while (current != 0) |
sam_grove | 0:3f64a15357ac | 180 | { |
sam_grove | 3:c14e7a918e21 | 181 | ++count; |
sam_grove | 0:3f64a15357ac | 182 | current = current->next; |
sam_grove | 0:3f64a15357ac | 183 | } |
sam_grove | 0:3f64a15357ac | 184 | |
sam_grove | 0:3f64a15357ac | 185 | return count; |
sam_grove | 0:3f64a15357ac | 186 | } |
sam_grove | 0:3f64a15357ac | 187 | |
sam_grove | 1:a032c0392ba1 | 188 | // pre-define the type for the linker |
sam_grove | 0:3f64a15357ac | 189 | template class LinkedList<node>; |
sam_grove | 0:3f64a15357ac | 190 | |
sam_grove | 0:3f64a15357ac | 191 | |
sam_grove | 0:3f64a15357ac | 192 | |
sam_grove | 0:3f64a15357ac | 193 | |
sam_grove | 0:3f64a15357ac | 194 |