Thursday, August 24, 2006

Linked Lists

Topics

• Linked lists versus arrays
• Using a struct  or  class to create a ListNode to hold data and the "next" pointer
• The list itself is represented by a single pointer, usually called "list" or "head"
• Each node in the list is an instance of the struct or an object of the ListNode class
• Linked Lists are almost always in dynamic memory, the heap.
• The list or head pointer points to the first node in the list.
• Each node of the linked list has a next pointer that points to the next node in the list.
• The next pointer of the last node is nulled, set to zero.
• Walking a linked list means following each pointer to the next node.
• Walking a linked list allows you to process the data in each node in the list.
• Circular linked lists
• Doubly linked lists
• Indexed linked lists
• A linked lists of linked lists

Readings

Chapter 3. Section 3.1, singly Linked Lists.