Basic Linked Lists Operations

A Node Data Type First we need a type that represents a node in a linked list Here is a sample node class in C++

 struct Node {  int  _data;  struct Node* _next; };

How to use this class We use this class to write a sample function that creates a linked list with three items

 struct Node* BuildSampleLinkedList() {  struct Node* firstNode = new struct Node();  struct Node* secondNode = new struct Node();  struct Node* thirdNode = new struct Node();   firstNode->_data = 100;  firstNode->_next = secondNode;   secondNode->_data = 200;  secondNode->_next = thirdNode;   thirdNode->_data = 50;  thirdNode->_next = NULL;   return firstNode; }

We can add a constructor to the struct and change the code in a way that there are only 7 assignments

 struct Node {  Node(){};   Node(int data, Node* next)  {   _data = data;   _next = next;  };   int  _data;  struct Node* _next; };  struct Node* SimplerBuildSampleLinkedList() {  return new struct Node(        100, new struct Node(200, new struct Node(50, NULL))); }

Although with enhanced compilers like Visual C++ 2005 these sorts of enhancements are considered obsolete Get the length of the list

 int ReturnLinkedListLength(struct Node* head) {  struct Node* itemNode = head;  int nodeCount = 0;  while(itemNode != NULL)  {   nodeCount++;   itemNode = itemNode->_next;  }   return nodeCount; }

This is also a sample of how we traverse all the nodes in a linked list Some Hints Here the itemNode is the variable that is considered the stack allocated representation of the whole Linked List. Q: What if we said head = NULL; at the end of Length() — would that mess up the myList variable in the caller? The answer is that the head variable that is passed to the function is the formal argument that is valued by the actual argument, in this case the pointer itself is passed by value, it means that we can use “head” directly inside of the body of the function instead of itemNode and it won’t change the original data Q: What if the passed in list contains no elements, does Length() handle that case properly? Yes it returns zero for NULL value of head. We add an insert method that adds a new node at the beginning of the list

 void AddNewHeadNodeInC(struct Node** head, int data) {  Node* newHeadNode = new Node(data, *head);  *head = newHeadNode; }  void AddNewHeadNodeInCPlusPlus(struct Node*&; head, int data) {  Node* newHeadNode = new Node(data, head);  head = newHeadNode;

}