【正文】 ode； newnode newnode last p last p （ Before） （ After） Linked List:Inserting a new node(4) Data Structure Software College Northeastern University int List::Insert ( const int x, const int i ) { // Insert a node with data equal to x after the i1?th ListNode *p = first。Data Structure Software College Northeastern University Chapter 3 Linked Lists Data Structure Software College Northeastern University Overview ?Linked Lists ?Programming details ?Common Error ?Doubly Linked Lists ? Circularly Linked Lists ? examples ? Cursors Implementation of Linked Lists Data Structure Software College Northeastern University Variablelength arrays? ?Direct access to element (By indexing) ?Array size is fixedlength To expand them, you create a new, longer array, and copy the contents of the old array into the new array ?This is used by function realloc() in C ?This is slow! ? Linear time Insertion/Removal due to shift elements ? due to contiguous storage in memory ?Half of the list needs to be moved for either operations Data Structure Software College Northeastern University Variablelength arrays? ?Solution: The list is not need to store contiguously. Attach a pointer to each item in the array, which points to the next item. provides the ability to add or remove the items anywhere in the list in constant time ?This is a linked list ?Linked lists are unbounded (maximum number of items limited only by memory) Data Structure Software College Northeastern University The Linked List data structure [0] [1] [2] array A B C Array Head A B C Linked list ? An data item plus its pointer is called a node ? 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 NULL ? a “head” which is a pointer to the first node in the linked list node Data Structure Software College Northeastern University ZHAO QIAN SUN LI ZHOU WU ZHENG WANG ^ H 43 13 1 NULL 37 7 19 25 Data Item Links LI QIAN SUN WANG WU ZHAO ZHENG ZHOU Address 1 7 13 19 25 31 37 43 31 H Header A simple single Linked List Data Structure Software College Northeastern University Memory Storage of linked list We can access all nodes through pointer “head” Heap Data Structure Software College Northeastern University Linked lists ? Each node contains the address of the next one in the list. ? We can access the first node through pointer “head” ? two important pointer: head: the reference to the first node tail: the reference to the last node Data Structure Software College Northeastern University How to implementate? Data Structure Software College Northeastern University Definition of the class ?Using multi class ? Class of Node(ListNode) ? Class of List ? Class of Iterator ?Type of Definition ? pound ? inside Data Structure Software College Northeastern University class List。 p→ link = newnode； newnode p newnode p （ Before） （ After） Linked List:Inserting a new node(3) Data Structure Software College Northeastern University ? Case 3： Insert in the rear newnode→ link = p→ link。 if ( p→ link == NULL ) last = newnode。 //if necessary update last k = q→ data。 item )。 Type *Remove ( int i )。 //鏈表置空，再刪去表頭結(jié)點(diǎn) } Implementation of linked list(3) Data Structure Software College Northeastern University template class Type void ListType :: MakeEmpty ( ) { //刪去鏈表中除表頭結(jié)點(diǎn)外的所有其他結(jié)點(diǎn) ListNodeType *q。 if ( i == 1 ) return first。 q = p→ link。 friend class ListIterator Type。 return current。 retval = 0 //指向第一個(gè)結(jié)點(diǎn) while ( p != null ){ //鏈表未掃描完 retval += *p。 Boolean Next ( )。 return (p!=first)?p:NULL。 int Prior ( )。 //循鏈搜索 if ( p != first ) { current = p。 //被刪結(jié)點(diǎn) current = current→ rLink。 return 0。 CursorSpace[0].next = CursorSpace[p].next。 return 1。 } current→ rLink→ lLink = current。 DblNodeType *p = first→ rLink。 Type getData ( ) const。 } Data Structure Software College Northeastern University template class Type CircListNodeType*List Type::Find ( Type value ) { //在鏈表中從頭搜索其數(shù)據(jù)值為 value的結(jié)點(diǎn) CircListNodeType *p = first→ link。 value )。 return NULL。amp。 ?Data member current point to the node currently used ? Iterator privides some test and find operation Data Structure Software College Northeastern University enum Boolean { False, True }。 p→ link = newnode。amp。 newnode → link = next。 //鏈表置空 int Length ( ) const。 Type data。 //q point the deleted node p = first = first→ link。 // Allocate memory for the new node Linked List:Inserting a new node(5) From 0 Data Structure Software College Northeastern University if ( first == NULL || i == 0 ) { //Insert in the front of list newnode→ link = first。 }。 }。 k i 1 ) { p = p→ link。 while ( p != NULL amp。 p→ link = newnode。 template class Type class List { ListNodeType *first, *last。 link = p。 //修改表尾指針 } Implementation of linked list(4) Data Structure Software College Northeastern University template class Type int ListType::Length ( ) const { //求單鏈表的長(zhǎng)度 ListNodeType *p = first→ link。 j i ) // j = i 停 { p = p→ link。 return amp。 }。 return NULL。 public: CircListNode ( Type d = 0, CircListNodeType *next = NULL ) : data ( d ), link ( next ) { } //構(gòu)造函數(shù) private: Type data。 p