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