LINKED LISTS AND POINTERS

• When someone cuts into the middle of a queue (array based), it leads to a domino-like effect forcing everyone behind the person to move: Insert Op
• When someone decides to leave the queue people behind have to move. Delete Op
• Data movement operations O(n)
• Linked list data structures improve processing efficiency.
• Tradeoff: space efficiency.

Linked Lists

• A collection of elements called nodes.
• Each node contains a data portion and a pointer.
• Data portion in all nodes are of the same type.
• Pointer in a node contains the location of the node.
• Entire list is referenced by a separate head pointer.
• Head pointer points to the first node in the list.
• Special value (NULL) is assigned to a pointer pointing to an empty linked list.
• Last node in the list contains a NULL pointer.

Head Previous Current Next Pointers

• To facilitate movement through the linked list two special pointers called previous and current are used.
• When list is empty previous and current are NULL.
• When list contains at least one node, head always points to the first node.
• Following an insertion operation, current points to the most recently inserted node.
• Following a removal operation, current points to the node after the most recently deleted node.
• Following a next operation, current points to the next node after the previous current one.

Initializing Pointer Variables

• A NULL pointer is represented in C++ as a value 0. By convention we use the symbolic constant NULL.
  constant NULL=0
• Pointer variable can be initialized as
  ptr =NULL;
• Pointer variable can be assigned the value of another pointer variable of the same type.
• Pointer variable can be initialized to point to its type.
  ptr = new int;

NEW

• new essentially asks the system to allocate memory for storing a value of the pointer's base type.
• Allows dynamic memory allocation as no space is reserved till run time.
  ptr=new int;

• if(ptr!=NULL){
  .....
  }
  else
  	cout <<``Error: no dynamic memory''<< endl;
  

Defining pointer types

• struct node;
  typedef node *node_ptr;
  struct node
  {
  	int data;
  	node_ptr next;	//previous: dbly linked.
  }
  node_ptr ptr;
  

Initializing Headers

• ptr=new node;
  cin>>ptr->data;
  ptr->next=NULL;
  

• get_node: Because it is important to initialize nodes properly, we have designed a function to make this task simple and consistent. When a new node is needed, call get_node.

• cin>>*ptr.data;
  *ptr.next=NULL;
  
  node_ptr get_node(int data);
  {
  	node_ptr temp=new node;
  	temp->data=data;
  	temp->next=NULL;
  	return temp;
  }
  

Example:

struct node;
typedef node *node_ptr;
struct node{int data;
		node_prt next;
	}
node_ptr p,q;

• p=get_node(1);
• q=get_node(2);
  p->next=q;p->data=5;
  p->next->data=66;
  p->->=get_node(7);

Example: Creating Lists

• Write a function that will create 10 nodes with integer values 1 to 10 and then links them in ascending order.

  p=get_node(10);
  for(int I=9;I<=1;--I)
  {
  	q=get_node(I);
  	q->next=p;
  	p=q;
  }
  

DELETE

• new initializes a pointer variable. Holds a dynamic memory value.
• delete returns a memory to the system stack.
  delete ptr;

Traverse a list

• void traverse()
  {
  	if(current!=NULL)
  	{
  		previous=current;
  		current=current->next;
  	}
  }
  

Insert in a list

• void insert(int data)
  {
  	node_ptr new_node=get_node(data);
  new_node->nest=current;
  if(current==head)
  	head=new_node;
  else
  	previous->next=new_node;
  current=new_node;
  }