Sergei G / LinkedList

Important changes to repositories hosted on mbed.com

Mbed hosted mercurial repositories are deprecated and are due to be permanently deleted in July 2026.

To keep a copy of this software download the repository Zip archive or clone locally using Mercurial.

It is also possible to export all your personal repositories from the account settings page.

Dependents:   JobScheduler

Fork of LinkedList by Sam Grove

LinkedList.cpp@6:e3ab7684c395, 2013-05-14 (annotated)

Committer:
sam_grove
Date:
Tue May 14 23:06:11 2013 +0000
Revision:
6:e3ab7684c395
Parent:
5:28e11c75b433
Child:
7:4ed66162aaa8
removed old code that was commented out

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