Jednosměrný seznam – C / C++ – Fórum – Programujte.com

Zdravím nevíte jak se implementuje jednosměrný seznam? Plus jak se v takovém seznamu implementuje přídávání prvků za hlavu? Nejlépe v C++.

Díky moc za pomoc

#1 Martin523
Tady máš nějakej základ, kterej by ti mohl pomoct posunout se dál.

#ifndef LINKEDLIST_H
#define LINKEDLIST_H

class LinkedListNode
{
	friend class LinkedList;
public:
	LinkedListNode()
	{
		m_data = 0;
		m_pNext = nullptr;
	}
	LinkedListNode(int data)
	{
		m_data = data;
		m_pNext = nullptr;
	}
	LinkedListNode(int data, const LinkedListNode* nextNode)
	{
		m_data = data;
		m_pNext = const_cast<LinkedListNode*>(nextNode);
	}
	LinkedListNode(LinkedListNode* other)
	{
		//přiřazení sebe sama
		if (this == other)
		{
			return;
		}

		m_data = other->m_data;
		other->m_data = 0;

		m_pNext = m_pNext;
		m_pNext->m_pNext = nullptr;
	}
protected:
private:
	int m_data;
	LinkedListNode * m_pNext;	
};

class LinkedList
{
public:
	LinkedList()
	{
		m_size = 0;
		m_pHead = nullptr;
	}
	LinkedList(int data)
	{
		m_size = 1;

		auto tmpNode = new LinkedListNode(data);
		m_pHead = tmpNode;
		m_pTail = tmpNode;
	}
	LinkedList(const LinkedListNode* newNode)
	{
		m_size = 1;
		m_pHead = const_cast<LinkedListNode*>(newNode);
		m_pTail = const_cast<LinkedListNode*>(newNode);
	}
	LinkedList(const LinkedList * other)
	{
		//přiřazení sebe sama
		if (this == other)
		{
			return;
		}

		m_size = other->m_size;
		auto tmpNode = other->m_pHead;

		while (tmpNode == nullptr)
		{
			auto newNode = new LinkedListNode(tmpNode);
			
			Add(newNode);
			tmpNode = tmpNode->m_pNext;
		}
	}
	void Add(int data)
	{
		if (m_size == 0)
		{
			auto newNode = new LinkedListNode(data);
			m_pHead = newNode;
			m_pTail = newNode;
			m_size = 1;
			return;
		}

		if (m_size == 1)
		{
			auto newNode = new LinkedListNode(data);			
			m_pTail = newNode;
			m_pHead->m_pNext = m_pTail;
			m_size++;
			return;
		}

		auto newNode = new LinkedListNode(data);
		m_pTail->m_pNext = newNode;
		m_pTail = newNode;
		m_size++;
	}
	void Add(const LinkedListNode* newNode)
	{
		if (m_size == 0)
		{
			m_pHead = const_cast<LinkedListNode*>(newNode);
			m_pTail = const_cast<LinkedListNode*>(newNode);
			m_size = 1;
			return;
		}

		if (m_size == 1)
		{
			m_pTail = const_cast<LinkedListNode*>(newNode);
			m_pHead->m_pNext = m_pTail;
			m_size++;
			return;
		}

		m_pTail->m_pNext = const_cast<LinkedListNode*>(newNode);
		m_pTail = const_cast<LinkedListNode*>(newNode);
		m_size++;
	}
	virtual ~LinkedList()
	{
		LinkedListNode * pTmp = m_pHead;

		while (pTmp != nullptr)
		{
			delete pTmp;
			pTmp = pTmp->m_pNext;
		}
	}
protected:
private:
	unsigned int m_size;
	LinkedListNode * m_pHead;
	LinkedListNode * m_pTail;
};

#endif

EDIT: Opravena chyba v Add metodě.

#1 Martin523
Jednodušší varianta 

struct Node
{
    int value;
    Node* next;

    Node() : next(NULL) {}
};

static Node* g_head = NULL;
static Node* g_last = NULL;

Node* createNode(int value)
{
    Node* n = new Node();
    n->value = value;
    return n;
}

void addNode(int value)
{
    Node* node = createNode(value);

    if (!g_head) {
        g_head = node;
    } else {
        g_last->next = node;
    }
    g_last = node;
}

int main()
{
    addNode(10);
    addNode(20);

    return EXIT_SUCCESS;
}

Další metody jako odebrání, vložení mezi nody apod. si zkus sám