Solved

Implementing a Linked List in C++

Posted on 1998-10-29
10
939 Views
Last Modified: 2008-03-06
How is the structure of a linked list class?
and how is it implemented in C++
0
Comment
Question by:kitsin
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
10 Comments
 
LVL 22

Expert Comment

by:nietod
ID: 1176459
Note we can provide only limited assistance in schoolwork problems.  We can answer specific questions, like you would ask your teacher.  We can review your work and make suggestions, again like your teacher would.

The first question I think is appropriate so I will answer that next.  The next is too broad, but I will answer it in part.

continues
0
 
LVL 22

Expert Comment

by:nietod
ID: 1176460
A linked list consists of a "head node pointer" and a list of zero or more "nodes"  

The "head node pointer" is simply a pointer to the first node in the list.  If the list is empty, that is if there are no nodes, then the head node pointer is set to NULL to indicate this.  (i.e if the head node pointer is NULL the list is empty.  If it is not NULL, there is at least one item in the list, maybe more, and the head node pointer points to the first one).

The nodes are stuctures or classes.  They contain two seperate types of information.  

They contain the information you want to store in the list and they contain the information used to maintain the list.  By "information you want to store in the list" I mean the data that you created the linked list to store for you.  For example, if this was a linked list of baseball players, the information might be a player;s name, age, and batting average.  Note that the node stores the information for a single "item" in the list.  That is, the list might store info for 100s of players, but a node stores information for only one player.  (You will need a 10 nodes to store information for a 100 players)

The other information the node contains is a the information used to maintain the list.  This is usually just a "next  node pointer"  (in singly linked lists, there are two pointers in doubly linked list and there can be other information is more exotic cases)  This pointer points to the next node in the list.  If the node is the last node in the list, then it has the value NULL to indicate that there are no more nodes after it.  

Thus with thus head node pointer and the next node pointers, you can see that the linked list is a chain, of sorts,   The head node pointer points to the first node in the chain.  Then that node points to the next.  and that one to the next and so on until your reach the end.

Does that make sense?  Let me know if you have questions.
0
 
LVL 22

Expert Comment

by:nietod
ID: 1176461
Opps that's usually my "sign-off", but there is a little more to say.  

In order to use the linked list, you must have "access to" the head node pointer.  That is how you find the first node (if there is one) and from there all the rest (if there are any).  Thus you must save the head node pointer in a variable that it is accessible when needed.  For a program that has a single linked list, for example, you mist save the head node pointer as a global variable that allows the linked list to be access from anywhere.  for a program that uses many linked lists, you might have a linked list class,  The class would store the head node pointer for the linked list it was using.

In most cases in C++ you would use a class to impliment the list.  As I said, the class stores the head node pointer (pointer to the 1st node).  It doesn't acutally store the nodes, it stores the information used to find them.  when an item is added to the list, the class will allocate space for a new node with "new" and will adjust the list pointers so that the item is part of the "chain".  similarly when an item is deleted.  It adjusts the pointers so the node is not in the chain, and then it "deletes" the node.  

Hopefully that can get you started.  Feel free to ask questions, but remember that I can provide only limited assistance.
0
Technology Partners: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

 

Author Comment

by:kitsin
ID: 1176462
It is too vague because I was looking for a scheme or a diagramatic structure  to implement the linked list, not the answer
0
 
LVL 22

Expert Comment

by:nietod
ID: 1176463
Ask me some questions, then...

It looks like this:

a linked list with 3 nodes, notice that the head pointer is a pointer to the first node and the last node's pointer is NULL.

Head pointer -> node1 -> node2->node3->NULL

An empty list.  Notice that the head pointer is just NULL.

Head pointer -> NULL

Reread what I wrote.  Then try to ask question from it.
0
 
LVL 1

Expert Comment

by:newexpert
ID: 1176464
You mean the STL container class list?
0
 
LVL 22

Expert Comment

by:nietod
ID: 1176465
No.  
0
 

Accepted Solution

by:
PavelY earned 100 total points
ID: 1176466
Hi,

Here's some source code for a linked list of some structure called Person.

The list has head and tail variables, which keep track of the first and last elements of the list.

// this is the list header file

class List {
      Person* head;
      Person* tail;

public:
      List();
      ~List();
      void AddHead(Person*);
      void AddTail(Person*);
      void AddAfter(Person*, Person*);
      Person* Find(const char*);
      void Delete(Person*);
      void DeleteAll();
      void ShowAll();
};

// here's the Person header (and cpp) file.

#include <iostream.h>
#include <string.h>

class Person {
      char fname[10];
      char lname[20];
      long num;

public:
      Person* next;
      Person() {
            next = NULL;
            SetFirstName("");
            SetLastName("");
            SetPhoneNum(0);
      }
      Person(char* name1, char* name2, long n) {
            next = NULL;
            SetFirstName(name1);
            SetLastName(name2);
            SetPhoneNum(n);
      }

      void SetFirstName(char* name) {
            if(strlen(name) < 10)
                  strcpy(fname, name);
      }
      void SetLastName(char* name) {
            if(strlen(name) < 20)
                  strcpy(lname, name);
      }
      void SetPhoneNum(long n) {
            num = n;
      }
      long GetPhoneNum() {
            return num;
      }
      char* GetFirstName() {
            return fname;
      }
      char* GetLastName() {
            return lname;
      }
      void Show() {
            cout << "First name: " << fname << "\n";
            cout << "Last name: " << lname << "\n";
            cout << "Phone: " << num << "\n";
      }
};

// and finally, the implementation of the List class:

#include "List.h"
#include "Person.h"

List::List() {
      head = tail = NULL;
}

List::~List() {
      DeleteAll();
}

void List::AddHead(Person* p) {
      if(head == NULL) {
            head = tail = p;
      }
      else {
            p->next = head;
            head = p;
      }
}

void List::AddTail(Person* p) {
      if(head == NULL) {
            head = tail = p;
      }
      else {
            tail->next = p;
            tail = p;
      }
}

Person* List::Find(const char* name) {
      for(Person* temp = head; temp; temp = temp->next)
            if(strcmp(temp->GetLastName(), name) == 0)
                  return temp;
      return NULL;
}

void List::Delete(Person* p) {
      if(p == head) {
            head = head->next;
            delete p;
            return;
      }
      for(Person* temp = head; temp; temp = temp->next)
            if(temp->next == p) {
                  temp->next = p->next;
                  delete p;
                  if(p == tail)
                        tail = temp;
                  break;
            }
      
}

void List::DeleteAll() {
      while(head)
            Delete(head);
}

void List::AddAfter(Person* ptr, Person* p) {
      Person* temp = ptr->next;
      ptr->next = p;
      p->next = temp;
      if(ptr == tail)
            tail = p;
}

void List::ShowAll() {
      for(Person* temp = head; temp; temp = temp->next) {
            temp->Show();
            cout << "\n";
      }
}

you can check it all with a main function like this:

#include "List.h"
#include "Person.h"

main() {
      List l;

      l.AddHead(new Person("Bugs", "Bunny", 100));
      
      Person* p = new Person("Hello", "Bye", 12939);
      l.AddTail(p);
      l.AddTail(new Person("Clark", "Kent", 2928));
      l.AddHead(new Person("Kermit","Frog", 121212));

      Person* p1 = l.Find("Frog");
      if(p1) {
            cout << "Found Frog!\n";
            p1->Show();
            l.AddAfter(p1, new Person("Bart", "Simpson", 999));
      }

      if(p1 = l.Find("Rabbit"))
            p1->Show();
      else
            cout << "Last name Rabbit does not exist!\n";

      l.Delete(l.Find("Kent"));

      cout << "\nDisplaying list:\n\n";
      l.ShowAll();

      return 0;
}

The person class has the next member pointing to the next one in the list.
Check out the source code. It really isn't that difficult!

Have fun!
  Pavel

0
 
LVL 22

Expert Comment

by:nietod
ID: 1176467
PavelY, this is for a homework assignment.  That answer is unappropriate and grounds for removal from experts exchange.
0
 

Expert Comment

by:flfmdll
ID: 1176468
And just so you know, nietod is very good at this stuff and windows programming.
0

Featured Post

Free Tool: Port Scanner

Check which ports are open to the outside world. Helps make sure that your firewall rules are working as intended.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

C++ Properties One feature missing from standard C++ that you will find in many other Object Oriented Programming languages is something called a Property (http://www.experts-exchange.com/Programming/Languages/CPP/A_3912-Object-Properties-in-C.ht…
This article shows you how to optimize memory allocations in C++ using placement new. Applicable especially to usecases dealing with creation of large number of objects. A brief on problem: Lets take example problem for simplicity: - I have a G…
The goal of the tutorial is to teach the user how to use functions in C++. The video will cover how to define functions, how to call functions and how to create functions prototypes. Microsoft Visual C++ 2010 Express will be used as a text editor an…
The viewer will be introduced to the technique of using vectors in C++. The video will cover how to define a vector, store values in the vector and retrieve data from the values stored in the vector.

751 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question