![]() ![]() Keep in mind, however, that pointers occupy space and that dynamic memory allocation incurs the overhead of function calls. Using dynamic memory allocation (instead of fixed-size arrays) for data structures that grow and shrink at execution time can save memory. Figure 21.2 illustrates a linked list with several nodes.įigure 21.2. Logically, however, the nodes of a linked list appear to be contiguous. Linked list nodes are normally not stored contiguously in memory. For example, it is typically more efficient to insert an item in a sorted linked list than a sorted array. The selection of a data structure is typically based on the performance of specific operations used by a program and the order in which the data items are maintained in the data structure. So accessing individual elements in a linked list can be considerably more expensive than accessing individual elements in an array. Linked lists do not afford such immediate "direct access" to their elements. This allows immediate access to any array element, because the address of any element can be calculated directly based on its position relative to the beginning of the array. The elements of an array are stored contiguously in memory. A linked list allows efficient insertion operations anywhere in the list. Insertion and deletion in a sorted array can be time consumingall the elements following the inserted or deleted element must be shifted appropriately. Existing list elements do not need to be moved. Linked lists can be maintained in sorted order by inserting each new element at the proper point in the list. Note that class template vector (introduced in Section 7.11) implements a dynamically resizable array-based data structure. Linked lists allow the program to adapt at runtime. Linked lists can provide better memory utilization in these situations. Linked lists become full only when the system has insufficient memory to satisfy dynamic storage allocation requests.Īn array can be declared to contain more elements than the number of items expected, but this can waste memory. The size of a "conventional" C++ array, however, cannot be altered, because the array size is fixed at compile time. Linked lists are dynamic, so the length of a list can increase or decrease as necessary. A linked list is appropriate when the number of data elements to be represented at one time is unpredictable. Lists of data can be stored in arrays, but linked lists provide several advantages. Stacks and queues are also linear data structures and, as we will see, can be viewed as constrained versions of linked lists. If nodes contain base-class pointers to base-class and derived-class objects related by inheritance, we can have a linked list of such nodes and use virtual function calls to process these objects polymorphically. A node can contain data of any type, including objects of other classes. ![]() Data is stored in a linked list dynamicallyeach node is created as necessary. By convention, the link pointer in the last node of a list is set to null ( 0) to mark the end of the list. Each subsequent node is accessed via the link-pointer member stored in the previous node. ![]() ![]() A linked list is accessed via a pointer to the first node of the list. A linked list is a linear collection of self-referential class objects, called nodes, connected by pointer linkshence, the term "linked" list. ![]()
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |