Singly linked lists (part 1)
This lesson contains approximately 18 minutes of video content.
An introduction to singly linked lists
Activity: Singly Linked List
Graded Playground Autograder
Activity Prompt:
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;
}
Submit is not supported in this site.