Linked list next method
In the previous lecture, we have seen some applications of the arrays. Arrays are nice and simple for storing things in a certain order, but they have drawbacks. In this lecture, we explore an important alternate implementation of the data structure that stores a sequence of elements -- linked list. Definition: A linked list is a collection of nodes that together form a linear ordering. It takes many different forms and implementation. In its most simplest form, a singly linked list is a linked list where each node is an object that stores a reference to an element and a reference, called next, to another node. Note that a node is defined in terms of itself, which is called self-referential structure. Terminologies:
Implementations: There are usually two forms of linked list:
Unlike an array, a singly linked list does not have a predetermined fixed size, and uses space proportional to the number of its elements. However, since we do not keep track of any index numbers for the nodes in a linked list, we cannot tell just by examining a node if it is the second, or fifth node in the list. Based on the above description of a singly linked list, what is the ADT for singly linked lists? Here is an implementation of the node of a singly linked list with elements as character strings. public class Node { private String element; // we assume elements are character strings private Node next; /** Creates a node with the given element and next node. */ public Node(String s, Node n) { element = s; next = n; } /** Returns the element of this node. */ public String getElement() { return element; } /** Returns the next node of this node. */ public Node getNext() { return next; } // Modifier methods: /** Sets the element of this node. */ public void setElement(String newElem) { element = newElem; } /** Sets the next node of this node. */ public void setNext(Node newNext) { next = newNext; } } And the following is an incomplete implementation of the singly linked list: /** Singly linked list .*/public class SLinkedList { protected Node head; // head node of the list protected long size; // number of nodes in the list /** Default constructor that creates an empty list */ public SLinkedList() { head = null; size = 0; } // ... update and search methods would go here ... } What about the case with a dummy head? /** Singly linked list .*/public class SLinkedList { protected Node head; // head node of the list protected long size; // number of nodes in the list /** Default constructor that creates an empty list */ public SLinkedList() { head = new Node(null, null); // create a dummy head size = 0; } // ... update and search methods would go here ... } |