数据结构英文教学课件：chapter3 Linked Lists

1、Software College Northeastern UniversityData StructureSoftware College Northeastern UniversityzLinked Lists zProgramming detailszCommon Error zDoubly Linked Lists z Circularly Linked Listsz examplesz Cursors Implementation of Linked ListsData StructureSoftware College Northeastern UniversityVariable

2、-length arrays?zDirect access to element (By indexing) zArray size is fixed-length -To expand them, you create a new, longer array, and copy the contents of the old array into the new arrayyThis is used by function realloc() in CyThis is slow!z Linear time Insertion/Removal due to shift elementsydue

3、 to contiguous storage in memory yHalf of the list needs to be moved for either operationsData StructureSoftware College Northeastern UniversityVariable-length arrays?zSolution: -The list is not need to store contiguously. -Attach a pointer to each item in the array, which points to the next item. -

4、provides the ability to add or remove the items anywhere in the list in constant timeyThis is a linked listyLinked lists are unbounded (maximum number of items limited only by memory)Data StructureSoftware College Northeastern UniversityThe Linked List data structure012arrayABCArrayHeadABCLinked lis

5、tz An data item plus its pointer is called a nodez A node contains data item and one or more links. - The link is a reference to a node. - The link of last node is set to NULLz a “head” which is a pointer to the first node in the linked list nodeData StructureSoftware College Northeastern University

6、ZHAOQIANSUNLIZHOUWUZHENGWANGH43131NULL3771925Data ItemLinksLIQIANSUNWANGWUZHAOZHENGZHOUAddress1713192531374331HHeaderA simple single Linked ListData StructureSoftware College Northeastern UniversityMemory Storage of linked listWe can access all nodes through pointer “head”Data StructureSoftware Coll

7、ege Northeastern Universityz Each node contains the address of the next one in the list.z We can access the first node through pointer “head”z two important pointer: - head: the reference to the first node - tail: the reference to the last nodeData StructureSoftware College Northeastern UniversityHo

8、w to implementate?Data StructureSoftware College Northeastern UniversityDefinition of the classData StructureSoftware College Northeastern University class List; class ListNode friend class List; private: int data; ListNode *link; ; class List public: private: ListNode *first, *last; ;List is a Frie

9、nd classData StructureSoftware College Northeastern UniversityListNode is a class inside ListData StructureSoftware College Northeastern UniversityLinked List:Inserting a new node(1)y Insert a node with data equal to x after the i-1th element. (i.e., when i = 1, insert the node as the first element;

10、 when index = 2, insert the node after the first element, and so on)y If the insertion is successful, return 1. Otherwise, return 0. (If index is length+1 of the list, the insertion will fail.)zSteps1.Locate i-1th element2. Allocate memory for the new node3. Point the new node to its successor4. Poi

11、nt the new nodes predecessor to the new nodenewNodeith elementData StructureSoftware College Northeastern UniversityzInsert positiony Case 1：insert in front of the first node newnodelink = first ; first = newnode； firstnewnodenewnodefirstLinked List:Inserting a new node(2)Data StructureSoftware Coll

12、ege Northeastern University newnodelink = plink; plink = newnode；newnodepnewnodepLinked List:Inserting a new node(3)Data StructureSoftware College Northeastern University newnodelink = plink; plink = last = newnode；newnodenewnodelastplastpLinked List:Inserting a new node(4)Data StructureSoftware Col

13、lege Northeastern University/ Insert a node with data equal to x after the i-1th / Locate i-1th elementAllocate memory for the new nodeLinked List:Inserting a new node(5)From 0Data StructureSoftware College Northeastern University if ( first = NULL | i = 0 ) /Insert in the front of list newnodelink

14、= first; if ( first = NULL ) last = newnode; first = newnode; else /else newnodelink = plink; if ( plink = NULL ) last = newnode; plink = newnode; return 1; Linked List:Inserting a new node(6)Data StructureSoftware College Northeastern University when we insert a new node： （1）insert before the ith e

15、lement， which pointer should we get first？ （2）illegal inserting position is ? How can we judge inserting position is illegal？ （3）We should change two links when inserting ， Is there an order？Linked List:Inserting a new nodeData StructureSoftware College Northeastern UniversityDelete the ith element

16、？Linked List:Deleting a new node(1)Data StructureSoftware College Northeastern Universityint List:Remove ( int i ) /Delete the ith element Node *p = first, *q; int k = 0; while ( p != NULL & k i-1 ) p = plink; k+; /locate the i-1th element if (i0 | p = NULL | plink = NULL ) cout “无效的删除位置无效的删除位置!n”;

17、return 0; if ( i = 0 ) /delete the first q = first; /q point the deleted node p = first = firstlink; /Update first Linked List:Deleting a new node(2)Data StructureSoftware College Northeastern University else q = plink; plink = qlink; if ( q = last ) last = p; /if necessary update last k = qdata; de

18、lete q; /free the node pointed by q return k;Linked List:Deleting a new node(3)Data StructureSoftware College Northeastern Universitylinking to the first node is called Header, the header cell only contains references to the first.0ana1firstlastfirst0lastData StructureSoftware College Northeastern U

19、niversity newnodelink = plink; if ( plink = NULL ) last = newnode; plink = newnode;Data StructureSoftware College Northeastern University q = plink; plink = qlink; delete q; if ( plink = NULL ) last = p;Data StructureSoftware College Northeastern UniversityTemplate of linked list(1)template class Li

20、st;template class ListNode friend class List; Type data; /结点数据结点数据 ListNode *link; /结点链接指针结点链接指针public: ListNode ( ); /链表结点构造函数链表结点构造函数 ListNode ( const Type& item ); ListNode *NextNode ( ) return link; /给出当前结点的下一结点地址给出当前结点的下一结点地址Data StructureSoftware College Northeastern Universityvoid InsertAfter

21、 ( ListNode *p ); /在当前结点后插入结点在当前结点后插入结点p ListNode *RemoveAfter ( ); /摘下当前结点的下一结点摘下当前结点的下一结点;template class List ListNode *first, *last;public: ListNode *GetNode ( const Type& item, ListNode *next ); /创建数据为创建数据为item，指针为，指针为next的新结点的新结点Template of linked list(2)Data StructureSoftware College Northeast

22、ern University List ( const Type & value ) last =first = new ListNode( value ); /构造函数构造函数 List ( ); /析构函数析构函数 void MakeEmpty ( ); /链表置空链表置空 int Length ( ) const; /求链表长度求链表长度 ListNode *Find ( Type value ); ListNode *Find ( int i ); int Insert ( Type value, int i ); Type *Remove ( int i ); Type *Get (

23、 int i ); Template of linked list(3)Data StructureSoftware College Northeastern Universitytemplate ListNode : ListNode ( ) : link (NULL) template ListNode:ListNode( const Type& item ) : data (item), link (NULL) template void ListNode:InsertAfter ( ListNode *p ) plink = link; link = p; Data Structure

24、Software College Northeastern Universitytemplate ListNode*ListNode:RemoveAfter ( ) /摘下当前结点的下一结点摘下当前结点的下一结点 ListNode *tempptr = link; if ( link = NULL ) return NULL; /没有下一结点则返回空指针没有下一结点则返回空指针 link = tempptrlink; /重新链接 return tempptr; /返回下一结点地址返回下一结点地址Data StructureSoftware College Northeastern Univer

25、sitytemplate ListNode*List:GetNode ( const Type& item, ListNode *next = NULL ) ListNode *newnode = new ListNode ( item ); newnode link = next; return newnode;template List : List ( )/析构函数析构函数 MakeEmpty ( ); delete first; /链表置空，再删去表头结点链表置空，再删去表头结点Data StructureSoftware College Northeastern University

26、template void List : MakeEmpty ( ) /删去链表中除表头结点外的所有其他结点删去链表中除表头结点外的所有其他结点 ListNode *q; while ( firstlink != NULL ) q = firstlink; firstlink = qlink; /将表头结点后第一个结点从链中摘下将表头结点后第一个结点从链中摘下 delete q; /释放它释放它 last = first; /修改表尾指针修改表尾指针Data StructureSoftware College Northeastern Universitytemplate int List:L

27、ength ( ) const /求单链表的长度求单链表的长度 ListNode *p = firstlink; /检测指针检测指针p指示第一个结点指示第一个结点 int count = 0; while ( p != NULL ) /逐个结点检测逐个结点检测 p = plink; count+; return count;Data StructureSoftware College Northeastern Universitytemplate ListNode*List :Find ( Type value ) /在链表中从头搜索其数据值为在链表中从头搜索其数据值为value的结点的结点

28、ListNode *p = firstlink; /检测指针检测指针 p 指示第一个结点指示第一个结点 while ( p != NULL & pdata != value ) p = plink; return p; / p 在搜索成功时返回找到的结点地址在搜索成功时返回找到的结点地址 / p 在搜索不成功时返回空值在搜索不成功时返回空值Data StructureSoftware College Northeastern Universitytemplate ListNode *List : Find ( int i ) /在链表中从头搜索第在链表中从头搜索第 i 个结点，不计头结点个结点

29、，不计头结点 if ( i -1 ) return NULL; if ( i = -1 ) return first; / i 应应 0 ListNode *p = firstlink; int j = 0; while ( p != NULL & j i ) / j = i 停停 p = plink; j+; return p;Data StructureSoftware College Northeastern Universitytemplate int List : Insert ( Type value, int i ) /将含将含的新元素插入到链表第的新元素插入到链表第 个位置个位

30、置 ListNode *p = Find ( i-1 ); / p 指向链表第指向链表第 i-1个结点个结点 if ( p = NULL ) return 0; ListNode *newnode = /创建结点创建结点 GetNode ( value, plink ); if ( plink = NULL ) last = newnode; plink = newnode; /重新重新链接链接 return 1;Data StructureSoftware College Northeastern Universitytemplate Type *List:Remove ( int i )

31、/从链表中删去第从链表中删去第 个结点个结点 ListNode *p = Find (i-1), *q; if ( p = NULL | plink = NULL ) return NULL; q = plink; plink = qlink; /重新链接重新链接 Type value = new Type ( qdata ); if ( q = last ) last = p; delete q; return &value;Data StructureSoftware College Northeastern Universitytemplate Type *List:Get ( int

32、i ) /提取第提取第 个结点的数据个结点的数据 ListNode *p = Find ( i ); / p 指向链表第指向链表第 个结点个结点 if ( p = NULL | p = first ) return NULL; else return & pdata;Data StructureSoftware College Northeastern UniversityArray versus Linked Listsz Linked lists are more complex to code and management than arrays, but they have some

33、distinct advantages.yDynamic: a linked list can easily grow and shrink in size.-We dont need to know how many nodes will be in the list. They are created in memory as needed.-In contrast, the size of a C array is fixed at compilation time.yEasy and fast insertions and deletions-To insert or delete a

34、n element in an array, we need to copy to temporary variables to make room for new elements or close the gap caused by deleted elements.-With a linked list, no need to move other nodes. Only need to reset some pointers.Data StructureSoftware College Northeastern UniversityArrays versus linked listsz

35、Space (storage) considerationsyA linked list requires pointers to nodesyAn array requires the maximum number of elements to be known in advance. If that maximum is not required, space is wasted at the end of the array.Data StructureSoftware College Northeastern UniversityArrays versus linked listszT

36、ime considerationsyMost methods in a linked list require more statements than those in an array, which may indicate more time requiredyArrays are quicker at finding and altering in the middleyLinked lists are quicker at additions and removals in the middleData StructureSoftware College Northeastern

37、UniversityzIterator class of list is used to traverse nodes of list.zpriciple：y Iterator class is friend of List and ListNodey Iterator refer to the nodes of list。yData member current point to the node currently usedy Iterator privides some test and find operationData StructureSoftware College North

38、eastern University enum Boolean False, True ;template class List;template class ListIterator;template class ListNode /表结点表结点friend class List ;friend class ListIterator ;public: private: Type data; ListNode *link; Template definition(1)Data StructureSoftware College Northeastern Universitytemplate c

39、lass List /链表类链表类public: private: ListNode *first, *last;template class ListIterator public: ListIterator ( const List & l ) : list ( l ), current ( l.first-link ) /构造函数构造函数: 引用链表引用链表 private: list list; ListNode * current;Template definition(2)Data StructureSoftware College Northeastern Universityt

40、emplate Boolean ListIterator : NotNull ( ) /检查链表中当前元素是否非空检查链表中当前元素是否非空 if ( current != NULL ) return True; else return False;currentcurrentcase 1 return True case 2 return FalseTemplate definition(3)Data StructureSoftware College Northeastern Universitytemplate Boolean ListIterator:NextNotNull ( ) /

41、检查链表中下一元素是否非空检查链表中下一元素是否非空 if ( current != NULL & currentlink != NULL ) return True; else return False; currentcurrentcase 1 return True case 2 return FalseTemplate definition(4)Data StructureSoftware College Northeastern Universitytemplate ListNode* ListIterator : Firster ( ) /返回链表中头结点的地址返回链表中头结点的地

42、址 current = list.first; return current;list.firstcurrent list with headerTemplate definition(5)Data StructureSoftware College Northeastern Universitytemplate Type * ListIterator : First ( ) /返回链表中第一个元素的地址返回链表中第一个元素的地址 if ( list.firstlink != NULL ) current = list.first-link; return ¤tdata; else

43、 current = NULL; return NULL; list.firstcurrent list with headerTemplate definition(5)Data StructureSoftware College Northeastern Universitytemplate Type* ListIterator : Next ( ) /返回链表中当前结点的下一个结点的地址返回链表中当前结点的下一个结点的地址 if ( current != NULL & currentlink != NULL ) current = currentlink; return & curren

44、tdata; else current = NULL; return NULL; currentcurrentTemplate definition(6)Data StructureSoftware College Northeastern Universityint sum ( const List &l ) ListIterator li ( l ); /链表为空时返回链表为空时返回0 int *p= li.First( ); retval = 0 /指向第一个结点指向第一个结点 while ( p != null ) /链表未扫描完链表未扫描完retval += *p; /累加累加 p=

45、 li.Next( ); return retval;Data StructureSoftware College Northeastern UniversityVariations of Linked ListszTwo problems - we cant get back to the beginning of the list - from the end, and we cant go backwards through the list. zSo, circular linked lists and doubly linked lists were invented.Data St

46、ructureSoftware College Northeastern UniversityVariations of Linked ListszCircular linked listsyThe last node points to the first node of the listyHow do we know when we have finished traversing the list? (Tip: check if the pointer of the current node is equal to the head.)HeadABData StructureSoftwa

47、re College Northeastern Universitytemplate class CircList;template class CircListNode friend class CircList;public: CircListNode ( Type d = 0, CircListNode *next = NULL ) : data ( d ), link ( next ) /构造函数构造函数private: Type data; CircListNode *link; Implementation of Circular linked lists(1)Data Struc

48、tureSoftware College Northeastern Universitytemplate class CircList public: CircList ( Type value ); CircList ( ); int Length ( ) const; Boolean IsEmpty ( ) return firstlink = first; Boolean Find ( const Type & value ); Type getData ( ) const; void Firster ( ) current = first; Boolean First ( ); Boo

49、lean Next ( ); Implementation of Circular linked lists(2)Data StructureSoftware College Northeastern University Boolean Prior ( ); void Insert ( const Type & value); void Remove ( );private: CircListNode *first, *current, *last;Implementation of Circular linked lists(3)Data StructureSoftware College

50、 Northeastern UniversityVariations of Circular Linked ListszCircular linked listsyconstruct an empty Circular linked list CircList ( const Type & value ) last =first = new CircListNode( value ); first-link = first; List ( const Type & value ) last =first = new ListNode( value ); Data StructureSoftwa

51、re College Northeastern Universitytemplate CircListNode*List :Find ( Type value ) /在链表中从头搜索其数据值为在链表中从头搜索其数据值为value的结点的结点 CircListNode *p = firstlink; /检测指针检测指针 p 指示第一个结点指示第一个结点 while ( p != first & pdata != value ) p = plink; return (p!=first)?p:NULL; / p 在搜索成功时返回找到的结点地址在搜索成功时返回找到的结点地址 / p 在搜索不成功时返回

52、空值在搜索不成功时返回空值Linked Lists: Searching in a CLLData StructureSoftware College Northeastern UniversityVariations of Linked ListszDoubly linked listsyEach node points to not only successor but the predecessoryThere are two NULL: at the first and last nodes in the listyAdvantage: given a node, it is easy

53、 to visit its predecessor. Convenient to traverse lists backwardsHeadABData StructureSoftware College Northeastern University Doubly linked listsData StructureSoftware College Northeastern Universitytemplate class DblList;template class DblNode friend class DblList;private: Type data; /数据数据 DblNode

54、*lLink, *rLink; /指针指针 DblNode ( Type value, /构造函数构造函数 DblNode *left, DblNode *right ) : data (value), lLink (left), rLink (right) Implementation of Doubly linked lists(1)Data StructureSoftware College Northeastern University DblNode ( Type value ) : data (value), lLink (NULL), rLink (NULL) ;template

55、 class DblList public: DblList ( Type uniqueVal ); DblList ( ); int Length ( ) const; int IsEmpty ( ) return firstrlink = first; int Find ( const Type & target ); Type getData ( ) const;Implementation of Doubly linked lists(2)Data StructureSoftware College Northeastern University void Firster ( ) cu

56、rrent = first; int First ( ); int Next ( ); int Prior ( ); int operator ! ( ) return current != NULL; void Insert ( const Type & value ); void Remove ( );private: DblNode *first, *current;Implementation of Doubly linked lists(3)Data StructureSoftware College Northeastern UniversityDoubly linked list

57、s:Data StructureSoftware College Northeastern UniversityDoubly Linked Lists:constructingtemplate DblList:DblLIst ( Type uniqueVal ) /双向循环链表的构造函数双向循环链表的构造函数, 创建表头结点创建表头结点 first = new DblNode ( uniqueVal ); firstrLink = firstlLink = first; current = NULL;Data StructureSoftware College Northeastern Uni

58、versitytemplate int DblList:Find ( const Type & target ) /在双向循环链表中搜索含在双向循环链表中搜索含target的结点，的结点，/搜索成功返回搜索成功返回1，否则返回，否则返回0。 DblNode *p = firstrLink; while ( p != first & pdata != target ) p = prLink; /循链搜索循链搜索 if ( p != first ) current = p; return 1; return 0;Doubly Linked Lists:searchingAnother method

59、?Data StructureSoftware College Northeastern University1. plLink = current;2. prLink =currentrLink;3. currentrLink = p;4. current = currentrLink;5. currentrLinklLink = current;Doubly Linked Lists:Inserting(1)Data StructureSoftware College Northeastern Universitytemplate void DblList:Insert ( const T

60、ype & value ) if ( current = NULL ) /空表情形空表情形 current = firstrLink = new DblNode ( value, first, first ); else /非空表情形非空表情形 currentrLink =new DblNode ( value, current, currentrLink ); current = currentrLink; currentrLinklLink = current;Doubly Linked Lists:Inserting(2)Data StructureSoftware College No