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");
}

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?

UserRevisionLine numberNew 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