Notes

Slide Show

Outline

1	Linked Lists in Action Chapter 5 introduces the often-used data public classure of linked lists. This presentation shows how to implement the most common operations on linked lists.
2	Declarations for Linked Lists For this presentation, each node in the linked list is a class, as shown here.
3	Declarations for Linked Lists The data portion of each node is an int.
4	Declarations for Linked Lists Each IntNode also contains a link which refers to another IntNode.
5	Declarations for Linked Lists A program can keep track of the front node by using a variable such as head in this example. Notice that head is not an IntNode -- it is a reference to an IntNode.
6	Declarations for Linked Lists A program can keep track of the front node by using an IntNode reference variable such as head. Notice that head is not an IntNode -- it is a reference to an IntNode. We represent the empty list by storing null in the head reference.
7	Inserting an IntNode at the Front We want to add a new entry, 13, to the front of the linked list shown here.
8	Inserting an IntNode at the Front Create a new node...
9	Inserting an IntNode at the Front Create a new node... Place the data in the new node's data field.
10	Inserting an IntNode at the Front Create a new node... Place the data in the new node's data field.... Connect the new node to the front of the list.
11	Inserting an IntNode at the Front
12	Inserting an IntNode at the Front
13	Inserting an IntNode at the Front
14	Inserting an IntNode at the Front
15	Inserting an IntNode at the Front
16	Inserting an IntNode at the Front
17	Inserting an IntNode at the Front
18	Inserting an IntNode at the Front
19	Caution! Always make sure that your linked list methods work correctly with an empty list.
20	Pseudocode for Inserting IntNodes IntNodes are often inserted at places other than the front of a linked list. There is a general pseudocode that you can follow for any insertion function. . .
21	Pseudocode for Inserting IntNodes Determine whether the new node will be the first node in the linked list. If so, then there is only one step:
22	Pseudocode for Inserting IntNodes
23	Pseudocode for Inserting IntNodes
24	Pseudocode for Inserting IntNodes What is the name of this link?
25	Pseudocode for Inserting IntNodes What is the name of this link ?
26	Pseudocode for Inserting IntNodes
27	Pseudocode for Inserting IntNodes Write one Java statement which will do the insertion.
28	Pseudocode for Inserting IntNodes Write one Java statement which will do the insertion.
29	Pseudocode for Inserting IntNodes Determine whether the new node will be the first node in the linked list. If so, then there is only one step:
30	Pseudocode for Inserting IntNodes The process of adding a new node in the middle of a list can also be incorporated as a separate method. This function is called addNodeAfter in the linked list toolkit of Section 4.2.
31	Pseudocode for Removing IntNodes IntNodes often need to be removed from a linked list. As with insertion, there is a technique for removing a node from the front of a list, and a technique for removing a node from elsewhere. We’ll look at the technique for removing a node from the front of a linked list.
32	Removing the Head IntNode
33	Removing the Head IntNode
34	Removing the Head IntNode
35	Removing the Head IntNode
36	Summary It is easy to insert or remove a node at the front of a list. You also need a technique for inserting or removing a node elsewhere
37	THE END