Created
October 24, 2017 19:36
-
-
Save yurii-litvinov/eb140756848491b54e1c263e7695108e to your computer and use it in GitHub Desktop.
Double-linked list implementation from programming class
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include "DoubleList.h" | |
struct DoubleListElement | |
{ | |
double value = 0.0; | |
DoubleListElement* prev = nullptr; | |
DoubleListElement* next = nullptr; | |
}; | |
struct DoubleList | |
{ | |
DoubleListElement* head = nullptr; | |
DoubleListElement* tail = nullptr; | |
unsigned size = 0; | |
}; | |
DoubleList *createDoubleList() | |
{ | |
return new DoubleList; | |
} | |
double value(DoubleListElement* position) | |
{ | |
return position->value; | |
} | |
void deleteDoubleList(DoubleList *&list) { | |
DoubleListElement* next = list->head; | |
while (next != nullptr) { | |
// временное хранилище следующего элемента | |
DoubleListElement* temp = next->next; | |
delete next; | |
next = temp; | |
} | |
delete list; | |
list = nullptr; | |
} | |
void addElement(double newValue, DoubleList* list, DoubleListElement* prevElement) { | |
// у нас есть указатель на элемент ПЕРЕД | |
// можем узнать элемент, стоящий ПОСЛЕ | |
DoubleListElement* nextElement = prevElement->next; | |
DoubleListElement* newElement = new DoubleListElement; | |
// создание нового элемента | |
newElement->value = newValue; | |
newElement->prev = prevElement; | |
newElement->next = nextElement; | |
// меняем предыдущий | |
prevElement->next = newElement; | |
// меняем последующий | |
if (nextElement != nullptr) { | |
nextElement->prev = newElement; | |
} | |
else { | |
list->tail = newElement; | |
} | |
list->size += 1; | |
} | |
void addNewHead(double newValue, DoubleList* list) { | |
DoubleListElement* newElement = new DoubleListElement; | |
//создани новую голову | |
newElement->value = newValue; | |
newElement->prev = nullptr; | |
newElement->next = list->head; | |
//список указывает на новую голову | |
list->head = newElement; | |
if (list->tail == nullptr) { | |
list->tail = newElement; | |
} | |
list->size += 1; | |
} | |
Position getTail(DoubleList* list) | |
{ | |
return list->tail; | |
} | |
Position getHead(DoubleList* list) | |
{ | |
return list->head; | |
} | |
bool isInTheEnd(Position a) | |
{ | |
return a == nullptr; | |
} | |
Position getNext(Position a) | |
{ | |
return a->next; | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#pragma once | |
struct DoubleListElement; | |
typedef DoubleListElement* Position; | |
struct DoubleList; | |
DoubleList *createDoubleList(); | |
void deleteDoubleList(DoubleList *&list); | |
// Returns value by given position. | |
double value(Position position); | |
double valueAt(DoubleList* list, int index); // | |
void addElementAt(double value, DoubleList* list, int index); // | |
void addElement(double newValue, DoubleList* list, Position pasteBefore); | |
void addNewHead(double newValue, DoubleList* list); | |
void deleteElement(Position index); | |
Position getHead(DoubleList* list); | |
Position getTail(DoubleList* a); | |
bool isInTheEnd(Position a); | |
Position getNext(Position a); |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include "stdafx.h" | |
#include <iostream> | |
#include "DoubleList.h" | |
using namespace std; | |
int main() | |
{ | |
DoubleList *sample = createDoubleList(); | |
addNewHead(0.0, sample); | |
for (double i = 1.0; i < 3.0; i++) | |
{ | |
addElement(i, sample, getTail(sample)); | |
} | |
for (Position i = getHead(sample); !isInTheEnd(i); i = getNext(i)) | |
{ | |
cout << value(i) << " "; | |
} | |
deleteDoubleList(sample); | |
return 0; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment