Bài giảng Data Structures & Algorithms - Chương 5: Linked Lists

Structure 2. Make linking between elements: 	- First, Last, Middle element 3. How many node to take all list elements, How to take all list. 4. Basic operations: - Insert new element (every position) - Delete (every position) - Count, Search, Sort, DeAllocated… - Data element - Link field element Single Linked List Data pNext Data pNext Data pNext Data pNext NULL 1. Structure struct Node { 	int data; 	Node *pNext; }; How to use node? Node node1; node1.data=10; node1.pNext=NULL; coutdata=20; node2->pNext=NULL; coutdata; delete node2; Compare??? What is the different? Delele and change address data pNext NULL data pNext data pNext data pNext Head Middle Last 2. The way to make link between elements First, last, middle element 3. How many node to take all list elements, how to take all list? data pNext NULL data pNext data pNext data pNext pHead Why? +from pHead, can we list all items? +from pHead, can we do everything with list: insert new, delete? +Do we need pTail? pTail 4. Basic operations: Initialize CreateNode SearchNode SizeOfList SumOfList SortList InsertFirst InsertLast InsertMid RemoveNode PrintList FreeMemory pHead only or pHead & pTail ??? Using pHead only Initialize typedef struct Node { int data; Node *pNext; }; typedef struct SingleList { Node *pHead; }; void Initialize(SingleList &list) { list.pHead=NULL; } CreateNode Node *CreateNode(int d) { Node *pNode=new Node; if(pNode!=NULL) { pNode->data=d; pNode->pNext=NULL; } else { coutpNext=list.pHead; list.pHead=pNewNode; } } 5 pNext InsertLast 9 pNext 8 pNext pHead NULL NULL 3 pNext pNode 5 pNext 9 pNext 8 pNext pHead NULL 3 pNext pNode 5 pNext 9 pNext 8 pNext pHead NULL 3 pNext pNode InsertLast void InsertLast(SingleList &list,int d) { Node *pNewNode=CreateNode(d); if(list.pHead==NULL) { list.pHead=pNewNode; } else { Node *pTmp=list.pHead; while(pTmp->pNext!=NULL) { pTmp=pTmp->pNext; } pTmp->pNext=pNewNode; } } 5 pNext InsertMid 9 pNext pHead NULL NULL pNode pIns pPre 8 pNext 10 pNext 3 pNext 5 pNext 9 pNext pHead pNode pIns pPre 8 pNext 10 pNext 3 pNext NULL InsertMid void InsertMid(SingleList &list,int pos,int d) { if(posSizeOfList(list)) { coutpNext; i++; } if(pPre==NULL) { pNewNode->pNext=list.pHead; list.pHead=pNewNode; } else { pPre->pNext=pNewNode; pNewNode->pNext=pTmp; } } RemoveNode- First 5 pNext 9 pNext 8 pNext pHead NULL 3 pNext 5 pNext 9 pNext 8 pNext pHead NULL 3 pNext 5 pNext 9 pNext 8 pNext pHead NULL 3 pNext NULL pDel pDel pDel 5 pNext 9 pNext pHead NULL 3 pNext RemoveNode- Not first 5 pNext 9 pNext 8 pNext pHead NULL 3 pNext 5 pNext 9 pNext 8 pNext pHead NULL 3 pNext pDel pRe pDel pRe 5 pNext 9 pNext 8 pNext pHead NULL 3 pNext pDel pRe NULL 9 pNext 8 pNext NULL 3 pNext pHead RemoveNode else { if(pPre==NULL) { Node *pDel=list.pHead; list.pHead=list.pHead->pNext; pDel->pNext=NULL; delete pDel; pDel =NULL; } else { pPre->pNext=pTmp->pNext; pTmp->pNext=NULL; delete pTmp; pTmp=NULL; } } } } void RemoveNode (SingleList &list,int d) { Node *pTmp=list.pHead; if(pTmp==NULL) { coutdata==d) break; pPre=pTmp; pTmp=pTmp->pNext; } if(pTmp==NULL) { coutdatapNext; } } 5 pNext 9 pNext 8 pNext pHead NULL 3 pNext SumOfList 5 pNext 9 pNext 8 pNext pHead NULL 3 pNext 8 9 5 3 int SumOfList(SingleList list) { Node *pTmp=list.pHead; int nSum=0; while(pTmp!=NULL) { nSum+=pTmp->data; pTmp=pTmp->pNext; } return nSum; } SizeOfList 5 pNext 9 pNext 8 pNext pHead NULL 3 pNext 1 2 3 4 int SizeOfList(SingleList list) { Node *pTmp=list.pHead; int nSize=0; while(pTmp!=NULL) { pTmp=pTmp->pNext; nSize++; } return nSize; } SearchNode 5 pNext 9 pNext 8 pNext pHead NULL 3 pNext 5 Input: Node * SearchNode(SingleList list,int d) { Node *pTmp=list.pHead; while(pTmp!=NULL) { if(pTmp->data==d) break; pTmp=pTmp->pNext; } return pTmp; } SortList 5 pNext 9 pNext 8 pNext pHead NULL 3 pNext 8 pNext 5 pNext 3 pNext pHead NULL 9 pNext Change by value Change by reference??? SortList Change by value void SortList(SingleList &list) { for(Node *pTmp=list.pHead;pTmp!=NULL;pTmp=pTmp->pNext) { for(Node *pTmp2=pTmp->pNext;pTmp2!=NULL;pTmp2=pTmp2->pNext) { if(pTmp->data>pTmp2->data) { int tmp=pTmp->data; pTmp->data=pTmp2->data; pTmp2->data=tmp; } } } } FreeMemory – Memory Leak void FreeMemory(SingleList &list) { coutpNext; pTmp->pNext=NULL; coutdata pNext=pNode; list.pTail=pNode; } } data Double Linked List pPre NULL pNext You can see in the one Node, it contains: Data; Previous and Next pointer data pPre pNext data pPre pNext NULL Basic operations: Initialize CreateNode SearchNode SizeOfList SumOfList SortList InsertFirst InsertLast InsertMid RemoveNode PrintList FreeMemory pHead only or pHead & pTail ??? Using pHead only Initialize typedef struct DNode { int data; DNode *pNext; DNode *pPrevious; }; typedef struct DoubleList { DNode *pHead; }; void Initialize(DoubleList &list) { list.pHead=NULL; } CreateNode DNode *CreateNode(int d) { DNode *pDNode=new DNode; if(pDNode!=NULL) { pDNode->data=d; pDNode->pNext=NULL; pDNode->pPrevious=NULL; } else {coutpNext=list.pHead; list.pHead->pPrevious=pDNode; list.pHead=pDNode; } } InsertLast pHead 8 pPre pNext 9 pPre pNext 5 pPre pNext NULL NULL pDNode 3 pPre pNext NULL NULL pHead 8 pPre pNext 9 pPre pNext 5 pPre pNext NULL pDNode 3 pPre pNext NULL NULL pHead 8 pPre pNext 9 pPre pNext 5 pPre pNext NULL pDNode 3 pPre pNext NULL InsertLast void InsertLast(DoubleList &list,int d) { DNode *pDNode=CreateNode(d); if(list.pHead==NULL) { list.pHead=pDNode; } else { DNode *pTmp=list.pHead; while(pTmp->pNext!=NULL) { pTmp=pTmp->pNext; } pTmp->pNext=pDNode; pDNode->pPrevious=pTmp; } } InsertMid pHead 8 pPre pNext 9 pPre pNext 5 pPre pNext NULL pDNode 3 pPre pNext NULL NULL 10 pPre pNext NULL pPre pIns pHead 8 pPre pNext 9 pPre pNext 5 pPre pNext NULL 10 pPre pNext NULL pPre pIns pDNode 3 pPre pNext NULL InsertMid pHead 8 pPre pNext 9 pPre pNext 5 pPre pNext NULL 10 pPre pNext NULL pPre pIns pDNode 3 pPre pNext pHead 8 pPre pNext 9 pPre pNext 5 pPre pNext NULL 10 pPre pNext NULL pPre pIns pDNode 3 pPre pNext InsertMid pHead 8 pPre pNext 9 pPre pNext 5 pPre pNext NULL 10 pPre pNext NULL pPre pIns pDNode 3 pPre pNext InsertMid void InsertMid(DoubleList &list,int pos,int d) { if(posSizeOfList(list)) { coutpNext=pTmp; pTmp->pPrevious=pDNode; list.pHead=pDNode;	 } else { pDNode->pNext=pTmp; pDNode->pPrevious=pTmp->pPrevious; pTmp->pPrevious->pNext=pDNode; pTmp->pPrevious=pDNode; } break;	 } pTmp=pTmp->pNext; i++; }} RemoveNode- First pDel pHead 8 pPre pNext 9 pPre pNext 5 pPre pNext NULL 10 pPre pNext NULL pDel pHead 8 pPre pNext 9 pPre pNext 5 pPre pNext NULL 10 pPre pNext NULL NULL pDel pHead 8 pPre pNext 9 pPre pNext 5 pPre pNext NULL 10 pPre pNext NULL NULL pHead 9 pPre pNext 5 pPre pNext 10 pPre pNext NULL NULL RemoveNode- Not first pDel pHead 8 pPre pNext 9 pPre pNext 5 pPre pNext NULL 10 pPre pNext NULL pDel pHead 8 pPre pNext 9 pPre pNext 5 pPre pNext NULL 10 pPre pNext NULL pDel pHead 8 pPre pNext 9 pPre pNext 5 pPre pNext NULL 10 pPre pNext NULL RemoveNode- Not first pDel pHead 8 pPre pNext 9 pPre pNext 5 pPre pNext NULL 10 pPre pNext NULL pDel pHead 8 pPre pNext 9 pPre pNext 5 pPre pNext NULL 10 pPre pNext NULL NULL NULL NULL pDel pHead 8 pPre pNext 9 pPre pNext 5 pPre pNext NULL 10 pPre pNext NULL NULL NULL RemoveNode else { pTmp->pPrevious->pNext 	=pTmp->pNext; if(pTmp->pNext!=NULL) pTmp->pNext->pPrevious 	=pTmp->pPrevious; pTmp->pPrevious=NULL; DNode *pNextToCheck=pTmp->pNext; pTmp->pNext=NULL; delete pTmp; pTmp=pNextToCheck; } } else pTmp=pTmp->pNext; } } void RemoveNode (DoubleList &list,int d) { DNode *pTmp=list.pHead; while(pTmp!=NULL) { if(pTmp->data==d) { if(pTmp==list.pHead) { list.pHead=list.pHead->pNext; pTmp->pNext=NULL; delete pTmp; pTmp=list.pHead; } PrintList void PrintList(DoubleList list) { Node *pTmp=list.pHead; if(pTmp==NULL) { coutdatapNext; } } pHead 8 pPre pNext 9 pPre pNext 5 pPre pNext NULL 10 pPre pNext NULL SumOfList 8 9 5 3 int SumOfList(DoubleList list) { Node *pTmp=list.pHead; int nSum=0; while(pTmp!=NULL) { nSum+=pTmp->data; pTmp=pTmp->pNext; } return nSum; } pHead 8 pPre pNext 9 pPre pNext 5 pPre pNext NULL 10 pPre pNext NULL SizeOfList 1 2 3 4 int SizeOfList(DoubleList list) { Node *pTmp=list.pHead; int nSize=0; while(pTmp!=NULL) { pTmp=pTmp->pNext; nSize++; } return nSize; } pHead 8 pPre pNext 9 pPre pNext 5 pPre pNext NULL 10 pPre pNext NULL SearchNode 5 Input: Node * SearchNode(DoubleList list,int d) { Node *pTmp=list.pHead; while(pTmp!=NULL) { if(pTmp->data==d) break; pTmp=pTmp->pNext; } return pTmp; } pHead 8 pPre pNext 9 pPre pNext 5 pPre pNext NULL 10 pPre pNext NULL SortList Change by value Change by reference??? pHead 8 pPre pNext 9 pPre pNext 5 pPre pNext NULL 10 pPre pNext NULL pHead 5 pPre pNext 8 pPre pNext 9 pPre pNext NULL 10 pPre pNext NULL SortList Change by value void SortList(DoubleList &list) { for(DNode *pTmp=list.pHead;pTmp!=NULL;pTmp=pTmp->pNext) { for(DNode *pTmp2=pTmp->pNext;pTmp2!=NULL;pTmp2=pTmp2->pNext) { if(pTmp->data>pTmp2->data) { int tmp=pTmp->data; pTmp->data=pTmp2->data; pTmp2->data=tmp; } } } } FreeMemory – Memory Leak void FreeMemory(DoubleList &list) { coutpNext; pDel->pNext=NULL; coutdata pNext=pDNode; pDNode->pPrevious=list.pTail; list.pTail=pDNode; } } DoubleList computeDoubleList(char *str) { 	DoubleList list; 	Initialize(list); 	for(int i=0;idata+tail2->data;	 	else if(tail1!=NULL) 	v1=tail1->data; 	else if(tail2!=NULL) 	v1=tail2->data; 	v1=v1+v2; 	 	if(v1>=10) 	{ 	v2=v1/10; 	v1=v1%10; 	} 	else 	v2=0;	 	InsertFirst(list,v1); 	if(tail1!=NULL) 	tail1=tail1->pPrevious; 	if(tail2!=NULL)	 	tail2=tail2->pPrevious;	 	} 	if(v2!=0) 	InsertFirst(list,v2); 	return list; } Circular Linked List Circular Last node point to first node Draw like Circle When using Circular single linked list Every node in list had the same position Needn’t Head, Tail END