Having Problems understanding Linked Lists(Singly) in C++ Can someone help out?

[struntz]

Hello everyone!!


I have been trying to find some good online tutorials of linked lists in C++. but all i have found where mainly C tutorials on ilinked lists, can someone give me a really simple example taht explains what everyhting does?



I understand pointers pretty well, i just don't understand the algorithum and whats going on becuase all the sample code i looked at was at least 150 lines of code or more.

Thanks for your time!

[CornedBee]

A liked list is mainly an object like this (C syntax, I'll do C++ later):

typedef struct _llnodetype
{
   int data; // use any type you want
   struct _llnodetype* pNext;
} LINKED_LIST_NODE;

typedef struct _lltype
{
  LINKED_LIST_NODE * pStart;
} LINKED_LIST;

Now that you have these two structures, you can define some functions to use them.

LINKED_LIST_NODE* GetFirst(LINKED_LIST* ll)
{
  return ll->pStart;
}

LINKED_LIST_NODE* GetNext(LINKED_LIST_NODE lln)
{
  return lln->pNext;
}

void AddHead(LINKED_LIST* ll, int data)
{
  LINKED_LIST_NODE* lln = (LINKED_LIST_NODE*)malloc(sizeof(LINKED_LIST_NODE));
  lln->data = data;
  lln->pNext = ll->pStart;
  ll->pStart = lln;
}

void AddTail(LINKED_LIST* ll, int data)
{ // more complicated, since we have to search the end
  LINKED_LIST_NODE *llnOld1, *llnOld2, *llnNew; // don't forget asterisks only count for the immediatly next variable
  for(llnOld1 = ll->pStart; llnOld1 != NULL; llnOld1 = llnOld1->pNext)
  {
    llnOld2 = llnOld1; // save value, if next is NULL it's too late
  }
  // llnOld2 now points to the last valid node
  llnNew = (LINKED_LIST_NODE*)malloc(sizeof(LINKED_LIST_NODE));
  llnNew->data = data:
  llnNew->pNext = NULL;
  llnOld2->pNext = llnNew;
}

// I'll leave the removeNode functions to you, don't forget to set invalid pointers to NULL

Now you're ready to use it!

// create the list simply by creating a LINKED_LIST object - either on the stack or the heap.
LINKED_LIST ll;

// important: set pStart to NULL
ll.pStart = NULL;

// you can now call functions
AddHead(&ll, 5);

In C++ you put all this into a class. You can also take advantage of nested classes (the node type would be a nested class of the linked list class) and templates (a linked list that is able to store everything).
Let me give you a short overview, this is a little like MFC CList:

// class header file

typedef void* POSITION; // black box access

template <class T> class CList
{
  // local private class
  struct CNode
  {
    T data;
    CNode* pNext;
  };
  // also private
  CNode* pStart;
  CNode* pEnd; // this makes AddTail easier

public:  // interface
  void AddHead(T data);
  void AddTail(T data);

  POSITION GetFirstNodePos();
  T GetNext(POSITION& pos);

  void RemoveHead();
  void RemoveTail();

  T GetAt(POSITION pos);
  T Insert(POSITION pos);

  // construction/destruction
  CList();
  ~CList();
};

// implementation
CList::CList()
{
pStart = NULL;
pEnd = NULL;
}

CList::~CList()
{
// search for any remaining elements and free their memory
}

implement the other functions, use new instead of malloc, and POSITION (=void*) is always cast to CNode*. Return only the data and never the object itself, and increment the value of pos in GetNext. See afxtempl.cpp in the MFC source code for the full implementation of a template-based double-linked list. It is much more complicated there, but this is not really necessary.

Any more questions?

[kedaman]

An algoritm is a step by step procedure, not quite the issue here. A linked list is a datastructure a simple example out of the OOP world. If you are unfamiliar with OOP then you should go learn some because it is enhances your programming capabilities.

A linked list is a very simple datastructure, a container with nodes linked to each other with pointers, each node containing an item.

Compared to arrays, resizing a linked list by inserting one or more elements is faster since old data won't need to be moved. Random access to linked lists is linear (slow) so generally you don't use lists for search purposes. Lists can be usefull for iterative access since each node contain pointer to the next.

A doublelinked list has nodes with pointers in both directions like this:

list -> [node] <-> [node] <-> [node] <-> [node] <- list

while a singlelinked list has nodes with pointers in a single direction:

list -> [node] -> [node] -> [node] -> [node] -> 0

While the doublelinked list can perform iteration in both direction and insert items from both sides, it also adds another 4 bytes per node for the extra pointer.Singlelinked lists are lighter and should be used unless you actually need to iterate in both directions.

[parksie]

Something about doubly-linked lists and XORing the prev and next pointers together springs to my mind, I just can't remember the details