数据结构讲义3.ppt

Data Structure Software College Northeastern University Chapter 3 Linked Lists Overview Linked Lists Programming details Common Error Doubly Linked Lists Circularly Linked Lists examples Cursors Implementation of Linked Lists Variable-length arrays? Direct access to element (By indexing) Array size is fixed-length -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 Variable-length 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) The Linked List data structure A simple single Linked List 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 Definition of the class Using multi class Class of Node(ListNode) Class of List Class of Iterator Type of Definition compound inside Linked List:Inserting a new node(1) int List::Insert ( const int x, const int i ) Insert a node with data equal to x after the i-1’th element. (i.e., when i = 1, insert the node as the first element; when index = 2, insert the node after the first element, and so on) If the insertion is successful, return 1. Otherwise, return 0. (If index is 1 or length+1 of the list, the insertion will fail.) Steps Locate i-1’th element Allocate memory for the new node Point the new node to its successor Point the new node’s predecessor to the new node Linked