Linked List
Juan Zhai juan.zhai@rutgers.edu
Java is Pass by Value
public static Node insert(Node front, int data){
//front stores the address 2000 when main calls insert()
Node node = new Node(data, front);//suppose node stores the address 2800
front = node; /*front stores 2800 because this assignment copies the address 2800 stored in node to front*/
return front; //return front which stores the address 2800
}
public static void set(Node front, int data){
front.data = data; /*front stores the address 2800, this assignment
updates the info field in the address 2800*/
}
public static void main(String[] args){
Node head = new Node(3, null); //suppose head stores the address 2000
head = insert(head,6); /*before assignment, head stores the address 2000, after assignment, head stores the address 2800,
so the list now has 6 and 3*/
set(head, 5); /*head stores the address 2800, the info stored in 2800
is changed to 5, so the list now has 5 and 3*/
}
Juan Zhai, juan.zhai@rutgers.edu 2
Object-oriented programming
• Whenweinsert/deletenodesfromalinkedlist,weneed to return front since the address stored in front may be updated. By returning front, the caller will know where to get the latest linked list.
• Whatifwewantthemethodtoreturnabooleanvalueto tell us whether the operation is successfully performed or not?
• Wearemanipulatingthelinkedlistthatispointedtoby front, is it possible that all the operations share front to avoid sending front back and forth?
Juan Zhai, juan.zhai@rutgers.edu 3
Object-oriented programming
• Object-orientedprogramming(OOP)isbasedonthe concept of objects.
• Eachobjectcontainsdata(intheformofinstance variables, known as attributes or properties), and operations (in the form of methods).
• Afeatureofobjectsisthatanobject’smethodscanaccess and modify the data fields of the object with which they are associated.
• Encapsulatealinkedlistobjectwithfrontasitsdataand insertion/deletion operations as its methods.
àunnecessary to pass front as a parameter any more Juan Zhai, juan.zhai@rutgers.edu 4
need object to call a non-static method
Use class name to call a static method
Juan Zhai, juan.zhai@rutgers.edu 5
public Class Node{
public String data;
public Node link;
public Node(int data,
Node next){
this.data = data;
this.link = link;
} }
public static void main(String[]
args){
LinkedList list = new
LinkedList();
list.addFront(“Apple”); list.addFront(“Banana”); list.addFront(“Orange”); list.print(); }
}
public Class LinkedList{
Node front;
public LinkedList(){
front = null;
}
public void print(){
Node ptr = front;
while (ptr != null) { System.out.println(ptr.data);
current = ptr.link;
}
public void addFront(int data){
Node node = new Node(data,
null);
node.link = front;
head = front;
}
Encapsulate data
Juan Zhai, juan.zhai@rutgers.edu 6
non-static methods
public static void main(String[] args){
Node list = new Node(); //list points to the first node
list = addFront(list, “Apple”);
list = addFront(list, “Banana”);
}
public static void main(String[] args){
LinkedList list = new LinkedList(); //list is an
object with the instance variable head which points to
the first node (encapsulate the data “head”)
list.addFront(“Apple”);
list.insertFront(“Banana”);
}
static methods: belong to Class, all objects have the same view, so just use class name to invoke static methods, no need to use objects: className.methodName(), className can be omitted if the method is called within the class.
non-static methods: different objects have different views (different values for different instance variables), need to invoke a method on an object: obj.methodName()
head is an instance variable
1. Non-static methods have access to head, so no need to pass head as a parameter 2. The modifications in the non-static methods are made to head and each object has
access to its instance variable (head) , so no need to return head
Juan Zhai, juan.zhai@rutgers.edu 7
Generics
• Define IntNode for integers, define StringNode for strings, is there a general way applicable for all data types?
• Define a class to accept objects of some generic type
• By convention, we use T and it stands for “template”
• A generic class is said to be a template that can be concretized to contain objects of any particular type when the generic class itself is instantiated
Juan Zhai, juan.zhai@rutgers.edu 10
Generics
//T: generic type parameter
public Class Node
public T info;
public Node link;
…
}
}
public class BookApp(){
… }
Juan Zhai, juan.zhai@rutgers.edu 11
public class LinkedList
Node
…
public void addFront(T o) {…}
public T get(int index) {…}
…
LinkedList
//instantiate the generic class
list.addFront(New Book(“Name”, “author”))
Book book = list.get(6);
//the retrieved item is a Book object
System.out.println(book.author);
Exceptions
public class LinkedList
throws: declare an exception in method signature, meaning likely to throw
Node
…
public T getFront() throws NoSuchElementException{
• •
Separate normal flow from error situations with exceptions
When an error occurs, create an exception and throw it to launch an
exceptional control flowJuan Zhai, juan.zhai@rutgers.edu 14
} }
if (front == null) {
// throw new NoSuchElementException();
throw new NoSuchElementException(“empty …”);
}return front.data; throw: throw an exception in method body explicitly. After executing throw statement, the control is given back to its caller (just like return), and the following
statements will not be executed.
• Refer to Sakai code for Linked List with generics and exceptions
Juan Zhai, juan.zhai@rutgers.edu 15
Doubly linked list
• A doubly linked list is a linked list in which each node has previous link that points to the previous node in the linked list
The previous link of the first node is null
public Class Node{
String data;
Node next;
Node prev;
}
Juan Zhai, juan.zhai@rutgers.edu 18
Insert after a specified node
public static void insertAfter(Node prevNode, String data) { //1. check whether the given previous node is null
if(prevNode == null)
throw new NullPointerException(“Previous node is NULL.”);
//2. create a new node with the given data
Node newNode = new Node(data);
//3. make the new node’s next point to the next node of prevNode newNode.next = prevNode.next;
//4. make the previous node’s next point to the new node prevNode.next = newNode;
//5. make the new node’s prev link point to the previous node newNode.prev = prevNode;
//6. make the new node’s next node’s prev point to the new node if(newNode.next != null)
}
newNode.next.prev J=uannZheaiw, juNano.zdhaei@;rutgers.edu 19
Delete a specified node in the middle
ptr.next.prev = ptr.prev;
ptr.prev.next = ptr.next;
Juan Zhai, juan.zhai@rutgers.edu 20
Circular Linked List rear
• A circular linked list is a linked list in which the last node refers back to the first node
• All the nodes are connected to form a circle
• There is no NULL at the end
• By keeping a pointer to the last entry, we have access to the first and last entry both in constant time.
• Last:rear
• First:rear.link
Juan Zhai, juan.zhai@rutgers.edu 21
Search target
public boolean search(String target) {
if(rear == null)
return false;
Node ptr = rear.next;
while(ptr != rear){
if(ptr.data == target)
return true;
ptr = ptr.next;
}
return rear.data == target;
}
rear
• Search from the first node.
• If there is only one node in the list, then rear.next is rear.
No iterations are performed. Comparison is done at last line.
Juan Zhai, juan.zhai@rutgers.edu 22
Search target
public boolean search(String target) {
if(rear == null)
return false;
Node ptr = rear;
do {
if(ptr.data == target)
return true;
ptr = ptr.next;
} while(ptr != rear)
return false;
}
rear
• Compare the last node and then search from the first node.
• If there is only one node in the list, then rear.next is rear.
One iteration is done to perform the comparison.
Juan Zhai, juan.zhai@rutgers.edu 23
Add Front
public void AddFront(String data) {
Node node = new Node(data, null);
if(rear == null){
rear = node;
rear.next = rear;
} else{
// no node, an empty list
node.next = rear.next;
rear.next = node;
}
}
rear
Juan Zhai, juan.zhai@rutgers.edu 24
Delete Front
public int deleteFront() throws NoSuchElementException{
if(rear == null) // no node, an empty list
throw new NoSuchElementException();
int tmp = rear.next.data;
if(rear == rear.next) //only one node
rear = null;
else
rear.next = rear.next.next; //at least two nodes
return tmp;
}
Juan Zhai, juan.zhai@rutgers.edu
25
rear