Skip to content

Instantly share code, notes, and snippets.

@yurii-litvinov
Created October 24, 2017 19:36
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save yurii-litvinov/eb140756848491b54e1c263e7695108e to your computer and use it in GitHub Desktop.
Save yurii-litvinov/eb140756848491b54e1c263e7695108e to your computer and use it in GitHub Desktop.
Double-linked list implementation from programming class
#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;
}
#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);
#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