#include <iostream>
#include <stdio.h>
using namespace std;
class Item
{
public:
int a;
};
class LinkList:public Item
{
LinkList *NextItem;
static LinkList *head;
public:
LinkList* GetNextItem();
LinkList* FindTail();
LinkList();
static LinkList* GetHead();
LinkList* AddNode();
void DeleteNode();
LinkList* Previous(LinkList* FinePrevious);
};
LinkList* LinkList::GetNextItem()
{
return this->NextItem;
}
LinkList* LinkList::GetHead()
{
return head;
}
LinkList* LinkList::Previous(LinkList* FinePrevious)
{
LinkList *temp = head;
LinkList *temp1 = head;
if(this==head)
{
return NULL;
}
while(temp->NextItem != FinePrevious)
{
temp1 = temp->NextItem;
temp = temp1;
}
return temp;
}
LinkList* LinkList::head = NULL;
LinkList::LinkList()
{
if(head==NULL)
head = this;
NextItem = 0;
}
LinkList* LinkList::AddNode()
{
LinkList *tail;
tail = FindTail();
tail->NextItem = new LinkList;
return tail->NextItem;
}
LinkList* LinkList::FindTail()
{
LinkList *temp = head;
LinkList *temp1 = head;
while(temp->NextItem != 0)
{
temp1 = temp->NextItem;
temp = temp1;
}
return temp;
}
void LinkList::DeleteNode()
{
LinkList *temp = Previous(this);
if(temp==NULL)
{
temp = head->NextItem;
delete head;
head = temp;
}
else
{
if(this->NextItem==0)
temp->NextItem = 0;
else
temp->NextItem = this->NextItem;
delete this;
}
}
void main()
{
LinkList *hey = new LinkList;
hey->a = 10;
LinkList *next = hey->AddNode();
next->a = 20;
LinkList *thing = hey->AddNode();
thing->a = 50;
LinkList* temp = hey;
LinkList* temp1;
while(temp!=0)
{
cout << temp->a << " ";
temp1 = temp->GetNextItem();
temp = temp1;
}
cout << endl;
thing->DeleteNode();
temp = LinkList::GetHead();
while(temp!=0)
{
cout << temp->a << " ";
temp1 = temp->GetNextItem();
temp = temp1;
}
cout << endl;
system("PAUSE");
}
LinkList (Help Almost Done)
Author
Ok This is the first attempt making a LinkList class and its almost complete but I running into a few problems. I want to make the link list class self contained as in everything that is needed by the linklist class such as knowing where is the head etc.. is in the linklist.
So my first problem is that I believe I achieved that but I had to make the linklist head a static pointer. The reason this is a problem is simply what happens if I want to make more then one linklist? they all will have the same head. I guess a way to fix this is by making it just a regular pointer and the constructure for each new item in the link list will have a parameter of the head variable from a object that will be in the same linklist but that looks to ugly so their must be another way.
My second problem is I dont want my linklist to inherit my data object (item class). I was guessing the Item could inherit the linklist but then the problem will be I would have to make the LinkList class be specific to the Item class and I was hoping to make it more generic as in I can use it for what ever class I want.
And my last problem is when I want to delete the entire list. I think the solution would simply be store the head in a temp variable pointer then simply delete the nextitem until all the other objects are gone and finally delete head. But how would I put this in the destructure? If I just put it in there it will try to delete the entire list everytime I delete a node. Because Im allowing the head of the linklist to change (its possible to delete the head and the next item will then become the head) I cant even specify for it to just delete everything if it is the head. I seen other places where the head is always the same and basically everything is added after the head so the head is just a place holder for the rest of the list. So any suggestions or help would be great. Thank You
Because you're using a pointer for the next item, I'm assuming you want to use a referenced based list.
Now, with the code you have given there are many problems...
1) You definitly shouldn't make the head static
2) You definitly shouldn't extend Node with your list
3) There is no need for the nextItem pointer
So, here is a quick thing of how the list should go... p.s., i'm making all data public to make the code cleaner, you should use accessors for get and set.
then in the cpp file
Now I know there are ways to make the list easier and this is by no means the most efficent way to implement it, but I'm at school and I don't have a lot of time. I don't have a chance to compile it and try it, but I think it would work without problems...
Also, in the main function when you go through all the list items, a list iterator would be perfect for that. You would implement another class say "Iterator" that would tell you if you had a next, and a getNext function for the list. You would then have this iterator as a data member of the linkedlist and reset it when needed.
p.s. I also see that you are using std in the top of your file, why not just use std::list.
p.p.s. If you need a full featured linkedlist and std:: wont work for you, just post and I'll post the code tonight when I have time, this is all off the top of my head
Now, with the code you have given there are many problems...
1) You definitly shouldn't make the head static
2) You definitly shouldn't extend Node with your list
3) There is no need for the nextItem pointer
So, here is a quick thing of how the list should go... p.s., i'm making all data public to make the code cleaner, you should use accessors for get and set.
class Node{public: int item; Node *next;};class LinkedList{private: Node *head; int numItems;public: LinkedList(); ~LinkedList(); Add(int item); Remove(int item); /* * other list things */};then in the cpp file
LinkedList::LinkedList(){ head=NULL; numItems = 0;}LinkedList::~LinkedList(){ Node *temp = head; while(temp != NULL) { delete temp; temp = temp.next; }}//insert a head of the list for fast inserting and because I have to tail nodevoid LinkedList::Add(int item){ Node *newNode = new Node(); newNode.item = item; if(numItems == 0) head = newNode; else { newNode.next = head; head = newNode; } numItems++;}//remove a node based on item//if multiple nodes have the same item, it removes the one put in latestvoid LinkedList::Remove(int item){ Node *prev = NULL; Node *temp = head; while(temp != NULL) { if(temp.item == item) break; prev = temp; temp = temp.next; } if(temp == NULL) return; if(prev == NULL) { head = temp.next; delete temp; return; } prev.next = temp.next; delete temp; }Now I know there are ways to make the list easier and this is by no means the most efficent way to implement it, but I'm at school and I don't have a lot of time. I don't have a chance to compile it and try it, but I think it would work without problems...
Also, in the main function when you go through all the list items, a list iterator would be perfect for that. You would implement another class say "Iterator" that would tell you if you had a next, and a getNext function for the list. You would then have this iterator as a data member of the linkedlist and reset it when needed.
p.s. I also see that you are using std in the top of your file, why not just use std::list.
p.p.s. If you need a full featured linkedlist and std:: wont work for you, just post and I'll post the code tonight when I have time, this is all off the top of my head
0) Your design has lots of problems, restrictions and oddities. Just use std::list and be done with it.
1) Using std::list is ridiculously easy:
2) Seriously, just use the standard library containers. I suspect the reason you're trying to write your own linked list is because you aren't even aware of other ways to implement a dynamically resizable container (since this condition is common, caused by a legacy of years of badly taught C classes). In the above code you can change the 'list' include to 'vector', change the typedef accordingly, and everything else still works with zero changes, and a completely different container implementation.
3) The fact that you wrote "void main()" in C++, and also included stdio.h when you don't even use it, suggests that you either yourself come from a C background or had teachers/references that did. You need to unlearn lots of garbage before you can consider yourself prepared to design this kind of stuff properly in C++. And smart people, having designed these things reasonably well in C++, throw them away and use the standard library. It's the *standard library*, you know. Don't tell me you want to crack open the C compiler and reinvent qsort() next?
1) Using std::list is ridiculously easy:
#include <list>#include <iostream>using namespace std;typedef list<int> Container;void main() { Container hey; // no need to heap-allocate, even hey.push_back(10); hey.push_back(20); hey.push_back(50); // and definitely no need to concern yourself with "nodes" in the calling // code, which is a HUGE failure of encapsulation. for (Container::iterator it = hey.begin(); it != hey.end(); ++it) { cout << *it << " "; } cout << endl; // Both loops in your example become basically the same thing with the // std::list. system("PAUSE");}2) Seriously, just use the standard library containers. I suspect the reason you're trying to write your own linked list is because you aren't even aware of other ways to implement a dynamically resizable container (since this condition is common, caused by a legacy of years of badly taught C classes). In the above code you can change the 'list' include to 'vector', change the typedef accordingly, and everything else still works with zero changes, and a completely different container implementation.
3) The fact that you wrote "void main()" in C++, and also included stdio.h when you don't even use it, suggests that you either yourself come from a C background or had teachers/references that did. You need to unlearn lots of garbage before you can consider yourself prepared to design this kind of stuff properly in C++. And smart people, having designed these things reasonably well in C++, throw them away and use the standard library. It's the *standard library*, you know. Don't tell me you want to crack open the C compiler and reinvent qsort() next?
Author
Im aware of STL and all the dynamic containers that i read about. But i figured learning how to make a linklist would give me a better understand on how it works etc... This isnt really for any practical program more of the programming and learning experience. Can you express what kind of specific problems with my design so I can learn from them.
Well your main problem is that you're trying to replicate a lisp style list, where the a list consists of a datavalue and a pointer to a list.
This approach isn't really appropriate for a language like C++ where the user is responsible for object lifetimes.
Have a look at the interface to std::list - it will give you a big clue into how a container class should look in C++.
This approach isn't really appropriate for a language like C++ where the user is responsible for object lifetimes.
Have a look at the interface to std::list - it will give you a big clue into how a container class should look in C++.
Supaflyfrank: Rather than pointing out the problems with your design, I'll try and give you an overview of the most common design pattern for a linked list. It won't, however, serve you as well as a good Data Structures coursebook and/or instructor would. Oh, and you're welcome to try looking at your compiler's implementation of std::list, but if you don't find it incredibly unreadable and hard to understand you're a better programmer than me.
At its simplest, a linked list consists of two structures -- a node structure, which holds the data, and a list structure, which holds (or, at least, points to) the nodes. Consider the following:
This code is an extremely simple "singly linked list" -- a linked list where each node has a single link, to the next node in the list. The list ends when a node's next pointer is 0/NULL.
You can traverse this list by starting at the head and jumping from one node to the next through the "next" links. For example, the following code uses a loop to jump from one node to the next until it reaches the end.
The last node's next pointer is 0, so once we reach it, the line in the loop will in effect make current_node set itself to 0, and end the loop.
Adding a node to the head of this LinkedList is simple enough.
The last two lines are where the important things happen -- FIRST, we make the new node's next pointer point to the list's current head node. Then we make the new node the head node.
One of the easiest things to mess up in a linked list is order of operations. Stiffler got this wrong in the destructor of his linked list class -- it deleted a node and then tried to access the next pointer of that node, which is decidedly undefined behavior. A correct way to delete all the nodes in our singly linked list would look like this:
Hopefully you can see that we have to SAVE the pointer to the next node, so that we can safely delete the current node and THEN "make the jump".
Inserting and deleting single nodes I will leave as a further exercise for the reader. With this singly linked list, you have to make sure and save the previous node as you're jumping down the list, so that you can set its next pointer to the new node (if you're inserting) or the node after the deleted node (if you're deleting). This is made a bit easier with a doubly linked list, where each node has a "next" pointer and a "previous" pointer. This also makes reverse and bidirectional iterators possible. If you can manage all that, you might also want to try a templated linked list class that can hold any data type (just like std::list), but that takes a decent knowledge of how C++ templates work.
Hope this helped,
JohnE / Twilight Dragon
At its simplest, a linked list consists of two structures -- a node structure, which holds the data, and a list structure, which holds (or, at least, points to) the nodes. Consider the following:
struct SinglyLinkedNode{ DataType data; Node* next;};struct LinkedList{ Node* head;};This code is an extremely simple "singly linked list" -- a linked list where each node has a single link, to the next node in the list. The list ends when a node's next pointer is 0/NULL.
You can traverse this list by starting at the head and jumping from one node to the next through the "next" links. For example, the following code uses a loop to jump from one node to the next until it reaches the end.
// assume we have previously created a LinkedList called "mylinkedlist" and// appended some itemsSinglyLinkedNode* current_node;current_node = mylinkedlist.head;while (current_node != 0){ current_node = current_node->next;}The last node's next pointer is 0, so once we reach it, the line in the loop will in effect make current_node set itself to 0, and end the loop.
Adding a node to the head of this LinkedList is simple enough.
SinglyLinkedNode* new_node = new SinglyLinkedNode;new_node->data = some_data;new_node->next = mylinkedlist.head;mylinkedlist.head = new_node;The last two lines are where the important things happen -- FIRST, we make the new node's next pointer point to the list's current head node. Then we make the new node the head node.
One of the easiest things to mess up in a linked list is order of operations. Stiffler got this wrong in the destructor of his linked list class -- it deleted a node and then tried to access the next pointer of that node, which is decidedly undefined behavior. A correct way to delete all the nodes in our singly linked list would look like this:
SinglyLinkedNode* current_node;SinglyLinkedNode* next_node;current_node = mylinkedlist.head;while (current_node){ next_node = current_node->next; delete current_node; current_node = next_node;}Hopefully you can see that we have to SAVE the pointer to the next node, so that we can safely delete the current node and THEN "make the jump".
Inserting and deleting single nodes I will leave as a further exercise for the reader. With this singly linked list, you have to make sure and save the previous node as you're jumping down the list, so that you can set its next pointer to the new node (if you're inserting) or the node after the deleted node (if you're deleting). This is made a bit easier with a doubly linked list, where each node has a "next" pointer and a "previous" pointer. This also makes reverse and bidirectional iterators possible. If you can manage all that, you might also want to try a templated linked list class that can hold any data type (just like std::list), but that takes a decent knowledge of how C++ templates work.
Hope this helped,
JohnE / Twilight Dragon
Author
Ok I have two question about single link list that might help me alot. Anytime you want to access anything from your link list do you go through the head node to start off? Is it possible to have a changing head node but then the rest of the nodes also know the updated head. And the main thing that confuses me is The idea of having two structure/class
One is the List class and the other is the class holding the data with a instance of the link list class. Now unless the Link List class has an instance of the data class how will the pointer to the next item in the link list class point to the next node the contains the data class i know that is confusing so i will try to show in code what I am saying
class LinkList
{
LinkList *head;
};
class Node
{
DataType data;
LinkList* next;
};
Node itemlist;
How can you get the itemlist object next to point to anything but another LinkList object which DOESNT contain the data object. I know I didnt explain that well so possibly if someone can post a link list that they created them selfs that has a changing head node and also uses class it will help me alot.
One is the List class and the other is the class holding the data with a instance of the link list class. Now unless the Link List class has an instance of the data class how will the pointer to the next item in the link list class point to the next node the contains the data class i know that is confusing so i will try to show in code what I am saying
class LinkList
{
LinkList *head;
};
class Node
{
DataType data;
LinkList* next;
};
Node itemlist;
How can you get the itemlist object next to point to anything but another LinkList object which DOESNT contain the data object. I know I didnt explain that well so possibly if someone can post a link list that they created them selfs that has a changing head node and also uses class it will help me alot.
Quote:Original post by Supaflyfrank
So my first problem is that I believe I achieved that but I had to make the linklist head a static pointer. The reason this is a problem is simply what happens if I want to make more then one linklist?
When you add your first element, if there is no head, make that element the head.
Quote:
My second problem is I dont want my linklist to inherit my data object (item class). I was guessing the Item could inherit the linklist but then the problem will be I would have to make the LinkList class be specific to the Item class and I was hoping to make it more generic as in I can use it for what ever class I want.
Off the top of my head, you could do something like this:
template <class T>class LinkedList{private: T* Head; T* Next;};or maybe:
template <class T>class Node{private: T* Element; T* Next;};template <class T>class LinkedList{private: Node<T>* Head;};or maybe even just:
template <class T>class Node : private T{private: T* Next;};template <class T>class LinkedList{private: Node<T>* Head;};These are just some quick thoughts, there's ALWAYS a better way to do things. :)
Daniel
If you're going to make a linkedlist class, then go for an STL approach. Introduce iterators.
Off the top of my head (so probably won't work straight out):
Off the top of my head (so probably won't work straight out):
template <typename T> class linked_list{public: template <typename T> class iterator { public: // friend classes/etc friend class linked_list<T>; public: // methods iterator() : current(NULL) { } T& operator *() { return *current.object; } const iterator& operator++() { current = current->next; return *this; } const iterator& operator--() { current = current->prev; return *this; } private: // methods (can be called by linked_list<T>) iterator(node<T> * n) : current(n) { } private: // members node<T> * current; };private: template <typename T> struct node { node * next; node * prev; T object; };public: // methods linked_list() : head(NULL), tail(NULL) { } ~linked_list() { // I'm not going to write cleanup code here. // it's easy to do. } iterator<T> * begin() { return iterator<T>(head); } iterator<T> * end() { return iterator<T>(tail); } const T& start() { return *head; } const T& finish() { return *tail; } void push_back(const T& t) { if (!head) { head = new node<T>; tail = head; } else { tail->next = new node<T>; tail = tail->next; } tail.object = t; tail = tail->next; }private: node<T> * head; node<T> * tail;};
This is what I've used in a linked list. Feel free to pick out anything you dont seem to have. It's probably not got stuff you did think of but I didn't. And to be honest it was heavily based on some code in a book .. just can't think of the title at the moment.
LinkedList.h
LinkedList.cpp
Example Program using it
LinkedList.h
#pragma once#include <windows.h>class CLinkedList{protected: CLinkedList* m_NextSibling; CLinkedList* m_PrevSibling; CLinkedList* m_Children; CLinkedList* m_Parent; int m_position;public: CLinkedList(void); ~CLinkedList(void); void SetNextSibling(CLinkedList* ListMember); void SetPrevSibling(CLinkedList* ListMember); void SetFirstChild(CLinkedList* ListMember); void SetParent(CLinkedList* ListMember); CLinkedList* GetNextSibling(void); CLinkedList* GetPrevSibling(void); CLinkedList* GetFirstChild(void); CLinkedList* GetParent(void); CLinkedList* AddChild(CLinkedList* ListMember); CLinkedList* RemoveChild(CLinkedList* ListMember); void RemoveAllChildren(void); int ChildCount(void);};LinkedList.cpp
#include <windows.h>#include ".\linkedlist.h"CLinkedList::CLinkedList(void){ this->SetNextSibling(NULL); this->SetPrevSibling(NULL); this->SetFirstChild(NULL);}CLinkedList::~CLinkedList(void){}void CLinkedList::SetNextSibling(CLinkedList* ListMember){ this->m_NextSibling = ListMember;}void CLinkedList::SetPrevSibling(CLinkedList* ListMember){ this->m_PrevSibling = ListMember;}CLinkedList* CLinkedList::GetNextSibling(void){ return this->m_NextSibling;}CLinkedList* CLinkedList::GetPrevSibling(void){ return this->m_PrevSibling;}void CLinkedList::SetFirstChild(CLinkedList* ListMember){ this->m_Children=ListMember;}CLinkedList* CLinkedList::GetFirstChild(void){ return this->m_Children;}void CLinkedList::SetParent(CLinkedList* ListMember){ this->m_Parent=ListMember;}CLinkedList* CLinkedList::GetParent(void){ return this->m_Parent;}CLinkedList* CLinkedList::AddChild(CLinkedList* ListMember){ ListMember->SetParent(this); int count=0; if (!this->m_Children) { this->m_Children = ListMember; this->m_position=1; } else { CLinkedList* temp = this->GetFirstChild(); while (temp->GetNextSibling()) { temp = temp->GetNextSibling(); count++; } temp->SetNextSibling(ListMember); ListMember->SetPrevSibling(temp); ListMember->m_position=count; } return ListMember;}CLinkedList* CLinkedList::RemoveChild(CLinkedList* ListMember){ CLinkedList* Temp = ListMember; CLinkedList* Next = Temp->GetNextSibling(); CLinkedList* Prev = Temp->GetPrevSibling(); ListMember = Next; Next = ListMember->GetNextSibling(); ListMember->SetPrevSibling(Prev); ListMember->SetNextSibling(Next); Prev->SetNextSibling(ListMember); return ListMember;}void CLinkedList::RemoveAllChildren(void){ this->SetFirstChild(NULL);}int CLinkedList::ChildCount(void){ int count=0; CLinkedList* temp = this->GetFirstChild(); while (temp) { CLinkedList* next = temp->GetNextSibling(); count++; temp = next; } return count;}Example Program using it
#include <stdio.h>#include <windows.h>#include "LinkedList.h"class CAnimals : public CLinkedList{public: char* Sound; char* Food; char* Name; void Display(void);}; CAnimals allanimals; CAnimals cat,dog,rat;void CAnimals::Display(void){ printf("This animal is named %s which makes a sound %s and eats %s\n",this->Name,this->Sound,this->Food);}void main(void){ cat.Food="wiskas"; cat.Sound="meow"; cat.Name="Tiddles"; allanimals.AddChild(&cat); dog.Food="chum"; dog.Sound="woof"; dog.Name="rover"; allanimals.AddChild(&dog); rat.Food="seeds"; rat.Sound="squeak"; rat.Name="Ben"; allanimals.AddChild(&rat); int count = allanimals.ChildCount(); printf("There are %d animals in this list\n\n",count); count=0; CAnimals* temp = (CAnimals*)allanimals.GetFirstChild(); while (temp) { CAnimals* next = (CAnimals*)temp->GetNextSibling(); count++; printf("Animal %d : \n",count); temp->Display(); temp = next; } allanimals.RemoveChild(&dog); count = allanimals.ChildCount(); printf("\n\nThere are %d animals in this list\n\n",count); count=0; printf("\n\n"); temp = (CAnimals*)allanimals.GetFirstChild(); while (temp) { CAnimals* next = (CAnimals*)temp->GetNextSibling(); count++; printf("Animal %d : \n",count); temp->Display(); temp = next; } allanimals.RemoveAllChildren(); count = allanimals.ChildCount(); printf("\n\nThere are %d animals in this list\n\n",count); count=0; printf("\n\n"); temp = (CAnimals*)allanimals.GetFirstChild(); while (temp) { CAnimals* next = (CAnimals*)temp->GetNextSibling(); count++; printf("Animal %d : \n",count); temp->Display(); temp = next; } char input='\0'; while (!input) scanf("%c",&input);}This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
