Thread: Linked Lists

Hi,

I was wondering how to write a linked list from scratch. It can't be too hard, I have about 80% of it down(from MUD programming) but I could never werite my own linked list from scratch. any suggestions?

I have a decent linked list at home I will post the source code when I get there.

Thanks, I coudl really use some source of a basic linked list.

A linked list is a container that holds instances of a struct/class. The struct/class has the interesting property of having a(t least one) pointer to it's own type, and usually a data member as well (why would anyone just have a group of pointers to other pointers????). Therefore the simplest linked list looks something like this (it will work in both C and C++):

#include <iostream.h>

struct node
{
char data;
node * next;
}

int main()
{
node * head;
return 0;
}

head can be considered to be the first node in a linked list list that has yet to be initialized and therefore useless from a practical standpoint (until something is done to it). Often in C++ programs the list is encapsulated in a class of it's own that includes all the functions necessary to manipulate the list such as adding new nodes to the list, deleting nodes from the list, displaying data stored in the list, sorting the data stored in the list, etc. etc. You have the freedom to design the list however you wish. You can use templated lists if you want them to be more general and there is a templated list class all done up for you in STL; you can have singly linked, doubly linked, and circular linked lists; the list can have a head node, tail node, current node, previous node, etc. etc. As usual, with all this freedom you have the responsibility of setting things up the way you wish.

Here's a basic linked list that creates 10 nodes, each holding a value of one greater than the previous node.

Code:

#inlcude <iostream.h>

class Node{
  public:
    int data;
    Node *next;  //declare the class for each node in the list
};                      //there must be a pointer to the next node.

int main(){
  Node Root=new Node;
  Node Iterator=new Node;  //Create two node objects, one as 
  Root->data=0;                  //the root node that doesn't change,
  Root->next=NULL;      //and the second as a node to traverse
                                     //the list.
  Iterator=Root;
  for(int i=1; i<10; i++){
    Iterator->next=new Node;
    Iterator=Iterator->next;       //traverse the list and add new 
    Iterator->data=i;              //nodes until there are 10 total
    Iterator->next=NULL;
  }

  Iterator=Root;
  while(Iterator!=NULL){
    cout<<Iterator->data;<<endl;  //print the list
    Iterator=Iterator->next;
  }
  return 0;
}

This is a singly linked list, meaning there is only one pointer for each node and that pointer points to the next node. The last node in the list points to NULL.

cpp

Hpp. Please note I had to save the extension the header as a .c or it wouldn't upload so just change it to LinkedList.hpp

thank you very much for your help! thats all I needed! =)