Solved

Implementing a Linked List in C++

Posted on 1998-10-29
10
924 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
10 Comments
 
LVL 22

Expert Comment

by:nietod
Comment Utility
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
Comment Utility
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
Comment Utility
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
 

Author Comment

by:kitsin
Comment Utility
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
Comment Utility
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
IT, Stop Being Called Into Every Meeting

Highfive is so simple that setting up every meeting room takes just minutes and every employee will be able to start or join a call from any room with ease. Never be called into a meeting just to get it started again. This is how video conferencing should work!

 
LVL 1

Expert Comment

by:newexpert
Comment Utility
You mean the STL container class list?
0
 
LVL 22

Expert Comment

by:nietod
Comment Utility
No.  
0
 

Accepted Solution

by:
PavelY earned 100 total points
Comment Utility
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
Comment Utility
PavelY, this is for a homework assignment.  That answer is unappropriate and grounds for removal from experts exchange.
0
 

Expert Comment

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

Featured Post

Why You Should Analyze Threat Actor TTPs

After years of analyzing threat actor behavior, it’s become clear that at any given time there are specific tactics, techniques, and procedures (TTPs) that are particularly prevalent. By analyzing and understanding these TTPs, you can dramatically enhance your security program.

Join & Write a Comment

What is C++ STL?: STL stands for Standard Template Library and is a part of standard C++ libraries. It contains many useful data structures (containers) and algorithms, which can spare you a lot of the time. Today we will look at the STL Vector. …
IntroductionThis article is the second in a three part article series on the Visual Studio 2008 Debugger.  It provides tips in setting and using breakpoints. If not familiar with this debugger, you can find a basic introduction in the EE article loc…
The viewer will learn how to pass data into a function in C++. This is one step further in using functions. Instead of only printing text onto the console, the function will be able to perform calculations with argumentents given by the user.
The viewer will learn additional member functions of the vector class. Specifically, the capacity and swap member functions will be introduced.

728 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

Need Help in Real-Time?

Connect with top rated Experts

14 Experts available now in Live!

Get 1:1 Help Now