【正文】 ster ( ) { //返回鏈表中頭結(jié)點(diǎn)的地址 current = 。 } current current case 1 return True case 2 return False Template definition(3) Data Structure Software College Northeastern University template class Type Boolean ListIteratorType::NextNotNull ( ) { //檢查鏈表中下一元素是否非空 if ( current != NULL amp。 l ) : list ( l ), current ( link ) { } //構(gòu)造函數(shù) : 引用鏈表 l, 表頭為當(dāng)前結(jié)點(diǎn) private: listType list。 }。 template class Type class ListNode { //表結(jié)點(diǎn) friend class List Type。 } Implementation of linked list(8) Data Structure Software College Northeastern University Array versus Linked Lists ?Linked lists are more plex to code and management than arrays, but they have some distinct advantages. ?Dynamic: a linked list can easily grow and shrink in size. We don?t 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 pilation time. ?Easy and fast insertions and deletions To insert or delete an 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 Structure Software College Northeastern University Arrays versus linked lists ?Space (storage) considerations ?A linked list requires pointers to nodes ?An 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 Structure Software College Northeastern University Arrays versus linked lists ?Time considerations ?Most methods in a linked list require more statements than those in an array, which may indicate more time required ?Arrays are quicker at finding and altering ?in the middle? ?Linked lists are quicker at additions and removals ?in the middle? Data Structure Software College Northeastern University Iterator class of list ?Iterator class of list is used to traverse nodes of list. ?priciple： ? Iterator class is friend of List and ListNode ? Iterator refer to the nodes of list。 } Implementation of linked list(8) Data Structure Software College Northeastern University template class Type Type *ListType::Get ( int i ) { //提取第 i 個(gè)結(jié)點(diǎn)的數(shù)據(jù) ListNodeType *p = Find ( i )。 if ( q == last ) last = p。 if ( p == NULL || p→ link == NULL ) return NULL。 if ( p→ link == NULL ) last = newnode。 } return p。 while ( p != NULL amp。 // p 在搜索成功時(shí)返回找到的結(jié)點(diǎn)地址 // p 在搜索不成功時(shí)返回空值 } Implementation of linked list(6) Data Structure Software College Northeastern University template class Type ListNodeType *ListType :: Find ( int i ) { //在鏈表中從頭搜索第 i 個(gè)結(jié)點(diǎn)，不計(jì)頭結(jié)點(diǎn) if ( i 1 ) return NULL。 //檢測(cè)指針 p 指示第一個(gè)結(jié)點(diǎn) while ( p != NULL amp。 while ( p != NULL ) { //逐個(gè)結(jié)點(diǎn)檢測(cè) p = p→ link。 //將表頭結(jié)點(diǎn)后第一個(gè)結(jié)點(diǎn)從鏈中摘下 delete q。 delete first。 item, ListNodeType *next = NULL ) { ListNodeType *newnode = new ListNodeType ( item )。 if ( link == NULL ) return NULL。 Template of linked list(3) Data Structure Software College Northeastern University template class Type ListNodeType :: ListNode ( ) : link (NULL) { } template class Type ListNodeType:: ListNode( const Typeamp。 int Insert ( Type value, int i )。 //析構(gòu)函數(shù) void MakeEmpty ( )。 item, ListNodeType *next )。 //在當(dāng)前結(jié)點(diǎn)后插入結(jié)點(diǎn) p ListNodeType *RemoveAfter ( )。 //鏈表結(jié)點(diǎn)構(gòu)造函數(shù) ListNode ( const Typeamp。 template class Type class ListNode { friend class ListType。 p→ link = q→ link。 } Linked List:Deleting a new node(3) Data Structure Software College Northeastern University Linked List with header ?A node linking to the first node is called Header, the header cell only contains references to the first. Nonempty list empty list 0 an a1 first last first 0 last Data Structure Software College Northeastern University Inserting in a linked list with header newnode→ link = p→ link。 } if ( q == last ) last = p。 } if ( i == 0 ) { //delete the first q = first。 k i1 ) { p = p→ link。 } Linked List:Inserting a new node(6) Data Structure Software College Northeastern University when we insert a new node： （ 1） insert before the i?th element， 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 node Data Structure Software College Northeastern University Case 1: delete the first Case 2: delete the other node Delete the i’th element According the pointer to i?th element ,Can we acplish the operation？ Linked List:Deleting a new node(1) Data Structure Software College Northeastern University int List::Remove ( int i ) { //Delete the i’th element Node *p = first, *q。 } else { //else newnode→ link = p→ link。 } ListNode *newnode= new ListNode(x, NULL)。 } // Locate i1?th element if ( i0 || p == NULL amp。 while ( p != NULL amp。 first = newnode； （ Before） （ After） first newnode newnode first Linked List:Inserting a new node(2) Data Structure Software College Northeastern University ? Case 2： insert in the middle of the list newnode→ link = p→ link。 ListNode *first, *last。 }。 private: int data。 class ListNode { friend class List。