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@11:4336cd18cce9, 2017-07-10 (annotated)

Committer:
sgnezdov
Date:
Mon Jul 10 16:46:46 2017 +0000
Revision:
11:4336cd18cce9
Parent:
8:918b196b0ac4 
tested descending order

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 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
sgnezdov 8:918b196b0ac4 61 template<class retT>
sgnezdov 11:4336cd18cce9 62 retT *LinkedList<retT>::insertOrdered(void *data, bool (isBigger)(void* data1, void *data2))
sgnezdov 8:918b196b0ac4 63 {
sgnezdov 8:918b196b0ac4 64 retT *new_node = new retT [1];
sgnezdov 8:918b196b0ac4 65 // make sure the new object was allocated
sgnezdov 8:918b196b0ac4 66 if (0 == new_node)
sgnezdov 8:918b196b0ac4 67 {
sgnezdov 8:918b196b0ac4 68 error("Memory allocation failed\n");
sgnezdov 8:918b196b0ac4 69 }
sgnezdov 8:918b196b0ac4 70 // store the address to the linked datatype
sgnezdov 8:918b196b0ac4 71 new_node->data = data;
sgnezdov 8:918b196b0ac4 72 // clear the next pointer
sgnezdov 8:918b196b0ac4 73 new_node->next = 0;
sgnezdov 8:918b196b0ac4 74 // check for an empty list
sgnezdov 8:918b196b0ac4 75 if (0 == _head)
sgnezdov 8:918b196b0ac4 76 {
sgnezdov 8:918b196b0ac4 77 _head = new_node;
sgnezdov 8:918b196b0ac4 78 printf("[insertAsc] set as head\n");
sgnezdov 8:918b196b0ac4 79 return new_node;
sgnezdov 8:918b196b0ac4 80 }
sgnezdov 8:918b196b0ac4 81
sgnezdov 8:918b196b0ac4 82 retT *current = _head;
sgnezdov 8:918b196b0ac4 83 retT *prev = 0;
sgnezdov 8:918b196b0ac4 84 // move to the item we want to insert
sgnezdov 8:918b196b0ac4 85 while (isBigger(data, current->data))
sgnezdov 8:918b196b0ac4 86 {
sgnezdov 8:918b196b0ac4 87 // while(true) execute the following
sgnezdov 8:918b196b0ac4 88 // data being inserted is smaller than current->data
sgnezdov 8:918b196b0ac4 89 if (0 == current->next) {
sgnezdov 8:918b196b0ac4 90 // there is no more data
sgnezdov 8:918b196b0ac4 91 printf("[insertAsc] insert at end\n");
sgnezdov 8:918b196b0ac4 92 current->next = new_node;
sgnezdov 8:918b196b0ac4 93 return new_node;
sgnezdov 8:918b196b0ac4 94 }
sgnezdov 8:918b196b0ac4 95 prev = current;
sgnezdov 8:918b196b0ac4 96 current = current->next;
sgnezdov 8:918b196b0ac4 97 }
sgnezdov 8:918b196b0ac4 98 if (0 == prev) {
sgnezdov 8:918b196b0ac4 99 printf("[insertAsc] insert at start\n");
sgnezdov 8:918b196b0ac4 100 new_node->next = _head;
sgnezdov 8:918b196b0ac4 101 _head = new_node;
sgnezdov 8:918b196b0ac4 102 return new_node;
sgnezdov 8:918b196b0ac4 103 }
sgnezdov 8:918b196b0ac4 104 printf("[insertAsc] insert inside\n");
sgnezdov 8:918b196b0ac4 105 new_node->next = current;
sgnezdov 8:918b196b0ac4 106 prev->next = new_node;
sgnezdov 8:918b196b0ac4 107 return new_node;
sgnezdov 8:918b196b0ac4 108 }
sam_grove 0:3f64a15357ac 109
sam_grove 0:3f64a15357ac 110 template<class retT>
sam_grove 0:3f64a15357ac 111 retT *LinkedList<retT>::append(void *data)
sam_grove 0:3f64a15357ac 112 {
sam_grove 0:3f64a15357ac 113 retT *current = _head;
sam_grove 0:3f64a15357ac 114 retT *new_node = new retT [1];
sam_grove 0:3f64a15357ac 115 // make sure the new object was allocated
sam_grove 0:3f64a15357ac 116 if (0 == new_node)
sam_grove 0:3f64a15357ac 117 {
Sissors 7:4ed66162aaa8 118 error("Memory allocation failed\n");
sam_grove 0:3f64a15357ac 119 }
sam_grove 0:3f64a15357ac 120 // store the address to the linked datatype
sam_grove 0:3f64a15357ac 121 new_node->data = data;
sam_grove 0:3f64a15357ac 122 // clear the next pointer
sam_grove 0:3f64a15357ac 123 new_node->next = 0;
sam_grove 0:3f64a15357ac 124 // check for an empty list
sam_grove 0:3f64a15357ac 125 if (0 == current)
sam_grove 0:3f64a15357ac 126 {
sam_grove 0:3f64a15357ac 127 _head = new_node;
sam_grove 0:3f64a15357ac 128 return _head;
sam_grove 0:3f64a15357ac 129 }
sam_grove 0:3f64a15357ac 130 else
sam_grove 0:3f64a15357ac 131 {
sam_grove 0:3f64a15357ac 132 // look for the end of the list
sam_grove 0:3f64a15357ac 133 while (current->next != 0)
sam_grove 0:3f64a15357ac 134 {
sam_grove 0:3f64a15357ac 135 current = current->next;
sam_grove 0:3f64a15357ac 136 }
sam_grove 0:3f64a15357ac 137 // and then add the new item to the list
sam_grove 0:3f64a15357ac 138 current->next = new_node;
sam_grove 0:3f64a15357ac 139 }
sam_grove 0:3f64a15357ac 140
sam_grove 0:3f64a15357ac 141 return current->next;
sam_grove 0:3f64a15357ac 142 }
sam_grove 0:3f64a15357ac 143
sam_grove 0:3f64a15357ac 144 template<class retT>
sam_grove 0:3f64a15357ac 145 retT *LinkedList<retT>::remove(uint32_t loc)
sam_grove 0:3f64a15357ac 146 {
sam_grove 0:3f64a15357ac 147 retT *current = _head;
sam_grove 1:a032c0392ba1 148 retT *prev = 0;
sam_grove 0:3f64a15357ac 149 // make sure we have an item to remove
sam_grove 5:28e11c75b433 150 if ((loc <= length()) && (loc > 0))
sam_grove 0:3f64a15357ac 151 {
sam_grove 0:3f64a15357ac 152 // move to the item we want to delete
sam_grove 3:c14e7a918e21 153 if (1 == loc)
sam_grove 0:3f64a15357ac 154 {
sam_grove 0:3f64a15357ac 155 _head = current->next;
sam_grove 0:3f64a15357ac 156 delete [] current;
sam_grove 0:3f64a15357ac 157 }
sam_grove 0:3f64a15357ac 158 else
sam_grove 0:3f64a15357ac 159 {
sam_grove 3:c14e7a918e21 160 for (uint32_t i=2; i<=loc; ++i)
sam_grove 0:3f64a15357ac 161 {
sam_grove 0:3f64a15357ac 162 prev = current;
sam_grove 0:3f64a15357ac 163 current = current->next;
sam_grove 0:3f64a15357ac 164 }
sam_grove 0:3f64a15357ac 165 // store the item + 1 to replace what we are deleting
sam_grove 0:3f64a15357ac 166 prev->next = current->next;
sam_grove 0:3f64a15357ac 167 delete [] current;
sam_grove 0:3f64a15357ac 168 }
sam_grove 0:3f64a15357ac 169 }
sam_grove 0:3f64a15357ac 170
sam_grove 0:3f64a15357ac 171 return _head;
sam_grove 0:3f64a15357ac 172 }
sam_grove 0:3f64a15357ac 173
sam_grove 0:3f64a15357ac 174 template<class retT>
sam_grove 0:3f64a15357ac 175 retT *LinkedList<retT>::pop(uint32_t loc)
sam_grove 0:3f64a15357ac 176 {
sam_grove 0:3f64a15357ac 177 retT *current = _head;
sam_grove 0:3f64a15357ac 178 // make sure we have something in the location
sam_grove 3:c14e7a918e21 179 if ((loc > length()) || (loc == 0))
sam_grove 0:3f64a15357ac 180 {
sam_grove 0:3f64a15357ac 181 return 0;
sam_grove 0:3f64a15357ac 182 }
sam_grove 0:3f64a15357ac 183 // and if so jump down the list
sam_grove 3:c14e7a918e21 184 for (uint32_t i=2; i<=loc; ++i)
sam_grove 0:3f64a15357ac 185 {
sam_grove 0:3f64a15357ac 186 current = current->next;
sam_grove 0:3f64a15357ac 187 }
sam_grove 0:3f64a15357ac 188
sam_grove 0:3f64a15357ac 189 return current;
sam_grove 0:3f64a15357ac 190 }
sam_grove 0:3f64a15357ac 191
sam_grove 0:3f64a15357ac 192 template<class retT>
sam_grove 0:3f64a15357ac 193 uint32_t LinkedList<retT>::length(void)
sam_grove 0:3f64a15357ac 194 {
sam_grove 3:c14e7a918e21 195 int32_t count = 0;
sam_grove 0:3f64a15357ac 196 retT *current = _head;
sam_grove 0:3f64a15357ac 197 //loop until the end of the list is found
sam_grove 0:3f64a15357ac 198 while (current != 0)
sam_grove 0:3f64a15357ac 199 {
sam_grove 3:c14e7a918e21 200 ++count;
sam_grove 0:3f64a15357ac 201 current = current->next;
sam_grove 0:3f64a15357ac 202 }
sam_grove 0:3f64a15357ac 203
sam_grove 0:3f64a15357ac 204 return count;
sam_grove 0:3f64a15357ac 205 }
sam_grove 0:3f64a15357ac 206
sam_grove 1:a032c0392ba1 207 // pre-define the type for the linker
sam_grove 0:3f64a15357ac 208 template class LinkedList<node>;
sam_grove 0:3f64a15357ac 209
sam_grove 0:3f64a15357ac 210
sam_grove 0:3f64a15357ac 211
sam_grove 0:3f64a15357ac 212
sam_grove 0:3f64a15357ac 213