Singly linked lists (part 1)
On this page
This lesson contains approximately 18 minutes of video content.
An introduction to singly linked lists
Implement the following member functions for the SinglyLinkedList class.
SinglyLinkedList Member Functions
| public | |
SinglyLinkedList() |
Default constructor |
~SinglyLinkedList() |
Destructor |
void PushBack(int value) |
Appends a Node whose data is value to the end of the linked list. |
void PushFront(int value) |
Adds a Node whose data is value to the beginning of the linked list. |
Be sure to update head_ and tail_ accordingly!
#include <iostream>
#include "singly_linked_list.hpp"
int main() {
/*
SinglyLinkedList sll;
std::cout << sll << std::endl;
sll.PushBack(11);
sll.PushBack(7);
sll.PushBack(8);
sll.PushFront(8);
std::cout << sll << std::endl;
*/
}
#ifndef SINGLY_LINKED_LIST_HPP
#define SINGLY_LINKED_LIST_HPP
#include <iostream>
#include "node.hpp"
class SinglyLinkedList {
public:
SinglyLinkedList();
~SinglyLinkedList();
void PushBack(int value);
void PushFront(int value);
friend std::ostream& operator<<(std::ostream& os,
const SinglyLinkedList& sll);
private:
Node* head_;
Node* tail_;
};
#endif
#include "singly_linked_list.hpp"
SinglyLinkedList::SinglyLinkedList() {
// TODO
}
SinglyLinkedList::~SinglyLinkedList() {
// TODO
}
void SinglyLinkedList::PushBack(int value) {
// TODO
}
void SinglyLinkedList::PushFront(int value) {
// TODO
}
#ifndef NODE_HPP
#define NODE_HPP
struct Node {
Node(int value): data(value) {}
int data = 0;
Node* next = nullptr;
};
#endif
#ifndef UTILITIES_HPP
#define UTILITIES_HPP
#include "singly_linked_list.hpp"
std::ostream& operator<<(std::ostream& os, const SinglyLinkedList& sll);
std::string Center(const std::string& str, unsigned int col_width);
#endif
#include "utilities.hpp"
#include <iomanip>
#include <sstream>
std::ostream& operator<<(std::ostream& os, const SinglyLinkedList& ll) {
Node* curr = ll.head_;
int field_size = 5;
os << '.' << std::setw(field_size) << std::setfill('-') << '.'
<< std::setfill(' ') << std::endl;
os << '|' << Center("Head", field_size - 1) << '|' << std::endl;
if (curr == nullptr)
os << ' ' << std::setw(field_size) << Center("--", field_size - 1) << ' '
<< std::setfill(' ') << std::endl;
while (curr != nullptr) {
os << '.' << std::setw(field_size) << std::setfill('-') << '.'
<< std::setfill(' ') << std::endl;
os << '|' << Center(std::to_string(curr->data), field_size - 1) << '|'
<< " " << curr << "\x1b[0m" << std::endl;
os << '\'' << std::setw(field_size) << std::setfill('-') << '\''
<< std::setfill(' ') << std::endl;
curr = curr->next;
if (curr != nullptr)
os << ' ' << std::setw(field_size) << Center("|", field_size - 1) << ' '
<< std::setfill(' ') << std::endl;
}
os << '|' << Center("Tail", field_size - 1) << '|' << std::endl;
os << '\'' << std::setw(field_size) << std::setfill('-') << '\''
<< std::setfill(' ') << std::endl;
return os;
}
std::string Center(const std::string& str, unsigned int col_width) {
// quick and easy (but error-prone) implementation
auto padl = (col_width - str.length()) / 2;
auto padr = (col_width - str.length()) - padl;
std::string strf = std::string(padl, ' ') + str + std::string(padr, ' ');
return strf;
}
> Click Run to compile and run your code.