Skip to content

Instantly share code, notes, and snippets.

@sigmadream
Last active May 16, 2024 05:00
Show Gist options
  • Save sigmadream/c372b19520f65658fd42b8e1da7134e1 to your computer and use it in GitHub Desktop.
Save sigmadream/c372b19520f65658fd42b8e1da7134e1 to your computer and use it in GitHub Desktop.

Haskell

module MyList where

data MyList a = Cons a (MyList a) 
                | MyNil deriving (Show, Eq)

myHead :: MyList a -> a
myHead l = case l of
        Cons a _ -> a

myTail :: MyList a -> MyList a
myTail MyNil = MyNil
myTail l = case l of
        Cons _ a -> a

myIndex :: Int -> MyList a -> a
myIndex 0 xs = myHead xs
myIndex x xs = myHead (myIndexTail x xs)
    where 
        myIndexTail 0 xs = xs
        myIndexTail i xs = myIndexTail (i-1) (myTail xs)

myLength :: MyList a -> Int 
myLength MyNil = 0
myLength xs = 1 + (myLength (myTail xs))

myLast :: MyList a -> a
myLast (Cons a MyNil) = a
myLast l = myLast (myTail l)

myInsert :: a -> MyList a -> MyList a
myInsert x xs = Cons x xs

myConcat :: MyList a -> MyList a -> MyList a
myConcat (Cons a MyNil) bs = Cons a bs
myConcat as bs = myInsert (myHead as) (myConcat (myTail as) bs)

myAppend :: a -> MyList a -> MyList a
myAppend x (Cons a MyNil) = Cons a (Cons x MyNil)
myAppend x xs = myInsert (myHead xs) (myAppend x (myTail xs))

myToList :: MyList a -> [a]
myToList MyNil = []
myToList (Cons a l) = a:(myToList l)

myFromList :: [a] -> MyList a 
myFromList [] = MyNil
myFromList l = Cons (head l) (myFromList (tail l))

myMapList :: (t -> a) -> MyList t -> MyList a
myMapList f (Cons x MyNil) = Cons (f x) MyNil
myMapList f l = Cons (f (myHead l)) (myMapList f (myTail l))

{-
 A simple linked list module
  Some examples: 
	mylist = (Cons 10 (Cons 99 (Cons 11 (Cons 1 MyNil))))
	myHead myList                       # => 10
	myTail myList                       # => Cons 99 (Cons 11 (Cons 1 MyNil))
	myLength myList               # => 4
	myToList myList               # => [10,99,11,1]
	myFromList [10,99,11,1]       # => (Cons 10 (Cons 99 (Cons 11 (Cons 1 MyNil))))
	myIndex 2 myList              # => 11
	myMapList (\x -> x*x) myList  # => Cons 100 (Cons 9801 (Cons 121 (Cons 1 MyNil)))
	...etc..
-}

C++

#include <iostream>
#include <sstream>

template<typename T>
struct Node
{
    T data;
    Node* next;
};


template<typename T>
class LinkedList
{
public:    
    Node<T>* m_head{nullptr};
    constexpr LinkedList() = default;
    ~LinkedList();
    [[nodiscard]] std::string toString() const;
    template<typename K>
    constexpr void insertFirst(const K& value);
    void insertFirst(const T& value);
    template<typename K>
    constexpr void insertLast(const K& value);
    void insertLast(const T& value);
    void removeFirst();
    [[nodiscard]] bool isEmpty() const { return m_head == nullptr; };
    void removeLast();
    [[nodiscard]] size_t size() const;

    friend std::ostream& operator<<(std::ostream& stream, const LinkedList& list)
    {
        stream << list.toString();
        return stream;
    }

};


template<typename T>
LinkedList<T>::~LinkedList()
{
    if (m_head != nullptr)
    {
        auto node = m_head->next;
        while (node != nullptr)
        {
            auto next = node->next;
            delete node;
            node = next;
        }

        m_head = nullptr;
    }
}

template<typename T>
template<typename K>
constexpr void LinkedList<T>::insertFirst(const K& value)
{
    (*this)->insertFirst(static_cast<T>(value));
}


template<typename T>
template<typename K>
constexpr void LinkedList<T>::insertLast(const K& value)
{
    (*this)->insertLast(static_cast<T>(value));
}


template<typename T>
void LinkedList<T>::insertFirst(const T& value)
{
    auto node = new Node<T>();
    node->data = value;

    if (m_head == nullptr)
    {
        m_head = node;
        m_head->next = nullptr;
    }
    else
    {
        auto temp = m_head;
        m_head = node;
        m_head->next = temp;
    }
}

template<typename T>
void LinkedList<T>::insertLast(const T& value)
{
    auto node = new Node<T>();
    node->data = value;
    node->next = nullptr;

    if (m_head == nullptr)
    {
        m_head = node;
        return;
    }

    auto temp = m_head;
    while (temp->next != nullptr)
    {
        temp = temp->next;
    }

    node->next = nullptr;
    temp->next = node;
}

template<typename T>
void LinkedList<T>::removeFirst()
{
    if (m_head == nullptr)
    {
        return;
    }

    m_head = m_head->next;
}

template<typename T>
void LinkedList<T>::removeLast()
{
    if (m_head == nullptr)
    {
        return;
    }

    if (m_head->next == nullptr)
    {
        delete m_head;
        return;
    }
    auto node = m_head;

    while (node->next->next != nullptr)
    {
        node = node->next;
    }

    delete node->next;
    node->next = nullptr;
}

template<typename T>
size_t LinkedList<T>::size() const
{
    auto   node    = m_head;
    size_t counter = 0;

    while (node != nullptr)
    {
        counter++;
        node = node->next;
    }

    return counter;
}

template<typename T>
std::string LinkedList<T>::toString() const
{
    std::stringstream stream;
    auto              node = m_head;
    if (node != nullptr)
    {
        while (node != nullptr)
        {
            stream << node->data << " -> ";
            node = node->next;
        }

    }
    stream << "NULL";
    return stream.str();
}

using LinkedListf  = LinkedList<float>;
using LinkedListd  = LinkedList<double>;
using LinkedListi  = LinkedList<int32_t>;
using LinkedListui = LinkedList<uint32_t>;
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment