27-11-2012, 01:03 PM
Linked Lists
1Linked Lists.ppt (Size: 1.24 MB / Downloads: 25)
Introducing Linked Lists
To insert or remove an element at an interior location in an ArrayList requires shifting of data and is an O(n) operation.
We need an alternative structure that stores elements in a sequence but allows for more efficient insertion and deletion of elements at random positions in the list. In a linked list , elements contain links that reference the previous and the successor elements in the list.
Structure of a Linked List
Each element is a node that consists of a value and a reference (link) to the next node in the sequence.
A node with its two fields can reside anywhere in memory.
The list maintains a reference variable, front, that identifies the first element in the sequence. The list ends when the link null ( ).
Creating a Linked List
Elements in a linked list are nodes. These are Node objects that have two instance variables. The first variable, nodeValue, is of generic type T. The second variable is a Node reference called next that provides a link to the next node
Linked lists are implementation structures and so Node objects are rarely visible in the public interface of a data structure. As a result, we declare the instance variables in the Node class public. This greatly simplifies the writing of code involving linked lists.
The Node class is a self‑referencing structure, in which the instance variable, next, refers to an object of its own type.
Creating a Linked ListThe Node Class
The class has two constructors that combine with the new operator to create a node. The default constructor initializes each instance variable to be null. The constructor with an type parameter initializes the nodeValue field and sets next to null.
Scanning a Linked List
Scan a singly linked list by assigning a variable curr the value of front and using the next field of each node to proceed down the list. Conclude with curr == null.
As an example of scanning a list, the static method toString() in the class ds.util.Nodes takes front as a parameter and returns a string containing acomma-separated list of node values enclosed in brackets.
Removing a Target Node
To remove the first occurrence of anode having a specified value, begin with a scan of the list to identify the location of the target node.
The scan must use a pair of references that move in tandem down the list. One reference identifies the current node in the scan, the other the previous (predecessor) node.
Doubly Linked Lists
Doubly-linked list nodes contain two references that point to the next and previous node.
Such a list has a reference, front, that points to the first node in the sequence and a reference, back, that points at the last node in the sequence.