Linked List
Juan Zhai juan.zhai@rutgers.edu
Linked List Operations
• Traverse the whole list • Search a specified item • Insert an item
• Delete an item
Juan Zhai, juanzhai@rutgers.edu 2
Traverse a linked list
• Basicoperationsofalinkedlistrequiretraversing the list
– Search the list for an item – Insert an item in the list
– Delete an item from the list
• Wecannotuseheadtotraversethelist
• We would lose the nodes of the list
• Use another reference variable of the same type as head to do the traversal: ptr
• Refer to Sakai code
Juan Zhai, juanzhai@rutgers.edu 3
Insertion
• Insert to the beginning of a linked list
• Insert to the end of a linked list
• Insert between two nodes of a linked list
Juan Zhai, juanzhai@rutgers.edu 4
Deletion
• Delete the first node of a linked list
• Delete the last node of a linked list
• Delete some in-between node of of a linked list.
Juan Zhai, juanzhai@rutgers.edu 5
Insert to the beginning
1. Createanewnode
2. Makethenewnodepointtothefirstnode of the original list
3. Makefront(thevariablewhichpointsto the first node of the list) point to the new node, otherwise the newly added node cannot be accessed
Refer to Sakai code
Juan Zhai, juanzhai@rutgers.edu 6
Remove the head
1. Makethefirstnodeheadpointtohead.link
public static IntNode deleteFront(IntNode front){ return front.next; //head has been changed
}
Work when the original list has only one node
What if the list is empty?
Juan Zhai, juanzhai@rutgers.edu 7
Remove the head
1. Makethefirstnodeheadpointtohead.link
public static IntNode deleteFront(IntNode front){
if (front == null) //watch out for empty list return null;
return front.next; //head has been changed }
Juan Zhai, juanzhai@rutgers.edu 8
Array v.s. Linked List
Operation
Array
Linked List
Traverse
O(n)
O(n)
Insert at beginning
O(n)
O(1)
Delete at beginning
O(n)
O(1)
• Constantorder:O(1),theexecutiontimedoesnot depend on the size of the input
• Linear order: O(n), the execution time increases at most linearly with the size of the input
Juan Zhai, juanzhai@rutgers.edu 9
Search a specified entry
1. Useavariabletoiterateoveritems
2. Stopsearchingif
a. The specified entry is found
b. Reach the end of the list
Refer to Sakai code
Juan Zhai, juanzhai@rutgers.edu 10
Insert after the integer target
1. Locate the node containing the specified integer target, denoted as ptr
2. Create a new node, denoted as n
3. Make the new node point to the node that follows target
àn.next = ptr.next
4. Make the node containing target point to the new node
àptr.next = n Refer to Sakai code
Juan Zhai, juan.zhai@rutgers.edu 11
1. 2.
Remove the specified integer
Locate the node that precedes the node containing the integer-to-be-deleted, denoted as ptr
Delink the node from the linked list
àptr.next = ptr.next.next
Juan Zhai, juan.zhai@rutgers.edu 12
Array v.s. Linked List
Operation
Array
Linked List
Search specified entry
O(n)
O(n)
Insert/delete at beginning
O(n)
O(1)
Insert/delete in middle*
O(n)
O(1)
* the search time is not included
Juan Zhai, juan.zhai@rutgers.edu 13
String Compare
• ==: compare object/reference, if refer to the same memory, result is true
• equals(): compare content, if the contents in the memories are the same, result is true
Juan Zhai, juan.zhai@rutgers.edu 14
0x2800
null
0x1000
0x3600
0x2000
front
Linked List Containing String
0x1000
0x2000
0x2800
…
“apple”
…
“banana”
…
“mango”
…
“orange”
…
Each string is a reference 0x3600 which points to the memory address that stores the actual string value like “apple”
Juan Zhai, juanzhai@rutgers.edu 15
Linked List Containing Strings
• How does code change if we need to have a linked list of Strings?
– Define a node class for data of String – Substitute == with .equals()
Refer to Sakai code
Juan Zhai, juanzhai@rutgers.edu 16