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@0:3f64a15357ac, 2013-04-04 (annotated)

Committer:
sam_grove
Date:
Thu Apr 04 20:34:38 2013 +0000
Revision:
0:3f64a15357ac
Child:
1:a032c0392ba1
Upload from different project and add documentation

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