【正文】 int IsEmpty ( ) { return first→ rlink == first。 Implementation of Doubly linked lists(2) Data Structure Software College Northeastern University void Firster ( ) { current = first。 int operator ! ( ) { return current != NULL。 private: DblNodeType *first, *current。 current = NULL。 while ( p != first amp。 return 1。 3. current→ rLink = p。 value ) { if ( current == NULL ) //空表情形 current = first→ rLink = new DblNode ( value, first, first )。 } Doubly Linked Lists:Inserting(2) Data Structure Software College Northeastern University 1. current→ rLink→ lLink = current→ lLink。 //下一結點 current→ lLink = temp→ lLink。 else current = current→ rLink。 count++。 } current = NULL。 } current = current→ rLink。 } current = current→ lLink。 }Node,CursorSpace[Spacesize]。 return p。 p = CursorSpace[0].next。 } Doubly Linked Lists:Changing Data Structure Software College Northeastern University DLL pared to SLL ?Advantages: ?Can be traversed in either direction (may be essential for some programs) ?Some operations, such as deletion and inserting before a node, bee easier ?Disadvantages: ?Requires more space ?List manipulations are slower (because more links must be changed) ?Greater chance of having bugs (because more links must be manipulated) Data Structure Software College Northeastern University Problem: ?Inserting or Deleting use new and delete to obtain and release a piece of space ?dynamic management ?If operations of getting or returning are frequently, it may indicate more time required Two resolving way: ?Cursor Implementation of linked lists using static memory ?Initially We allocate many nodes to linked into spare lists Linked Lists: Cursor Implementation Data Structure Software College Northeastern University Tow important features of linked list: ?The data are stored in a collection of structure, each structure contains data and a pointer to the next structure ?A new structure can be obtained from the system?s global memory by a call to new and released by a call to delete Implementation: ?Have a global array of structure ?Array index can be used in place of an address Linked Lists: Cursor Implementation Data Structure Software College Northeastern University Global array of structures Address: Array index 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 0 define SpaceSize 1000 typedef struct Node{ ElementType data。 } Doubly Linked Lists:Changing Data Structure Software College Northeastern University template class Type int DblListType::Prior ( ) { if ( current→ lLink == first ) { current = NULL。 } template class Type int DblListType::Next ( ) { if ( current→ rLink == first ) { current = NULL。 } Doubly Linked Lists:counting Data Structure Software College Northeastern University template class Type int DblListType::First ( ) { if ( !IsEmpty ( ) ) //跳過表頭結點的第一個 { current = first→ rLink。 int count = 0。 delete temp。 1 2 Doubly Linked Lists:Deleting(1) Data Structure Software College Northeastern University template class Type void DblListType::Remove ( ) { if ( current != NULL ) { DblNode *temp = current。 current = current→ rLink。 5. current→ rLink→ lLink = current。 } Doubly Linked Lists:searching Another method? Data Structure Software College Northeastern University 1. p→ lLink = current。 p→ data != target ) p = p→ rLink。 target ) { //在雙向循環(huán)鏈表中搜索含 target的結點， //搜索成功返回 1，否則返回 0。 Implementation of Doubly linked lists(3) Data Structure Software College Northeastern University Doubly linked lists:Searching Data Structure Software College Northeastern University Doubly Linked Lists:constructing template class Type DblListType::DblLIst ( Type uniqueVal ) { //雙向循環(huán)鏈表的構造函數 , 創(chuàng)建表頭結點 first = new DblNodeType ( uniqueVal )。 value )。 int Next ( )。 target )。 ~DblList ( )。 private: Type data。 p→ data != value ) p = p→ link。 value ) { last =first = new ListNodeType( value )。 插入 Implementation of Circular linked lists(3) Data Structure Software College Northeastern University Variations of Circular Linked Lists ?Circular linked lists ?construct an empty Circular linked list CircList ( const Type amp。 value)。 } Boolean First ( )。 } Boolean Find ( const Type amp。 } Implementation of Circular linked lists(1) Data Structure Software College Northeastern University template class Type class CircList { public: CircList ( Type value )。 } Calculating using iterator Data Structure Software College Northeastern University Variations of Linked Lists ?Two problems we can?t get back to the beginning of the list from the end, and we can?t go backwards through the list. ?So, circular linked lists and doubly linked lists were invented. Data Structure Software College Northeastern University Variations of Linked Lists ?Circular linked lists ?The last node points to the first node of the list ?How do we know when we have finished traversing the list? (Tip: check if the pointer of the current node is equal to the head.) Head A B Data Structure Software College Northeastern University template class Type class CircList。 //鏈表為空時返回 0 int *p= ( )。 } else { current = NULL。amp。current→ data。 } current current case 1 return True case 2 return False Template definition(4) Data Structure Software College Northeastern University template class Type ListNodeType* ListIteratorType :: Fir