CSC508 Data Structures

Topic 4 : Linked List Variation

Compiled & edited by: Zahid Zainal

 Recap

 Linked list
 Definition
 Characteristics
 Properties
 LinkedList class
 Linked list operation

Compiled & edited by: Zahid Zainal

 Topic Structure

 Improving Linked List

 Doubly Linked
 Circular Linked List
 Multidimensional Linked List

Compiled & edited by: Zahid Zainal

 Learning Outcomes

 At the end of this lesson, students should be able to:

 Explain improvement needed for linked list efficiency
 Describe variation of linked lists
 Compare the need for array and linked lists

Compiled & edited by: Zahid Zainal

 Improving Linked List

 Inserting a new item at beginning of a linked list is fast

(no traversal required)

X X
lastNode

newNode newNode

 While inserting at the end of the list required us to

traverse the whole list to reach the last element
 If in a program there is a need to frequently insert items
at end of the list, it’s worth to change the data structure
to allow more efficient implementation
Compiled & edited by: Zahid Zainal
 Improving Linked List (cont.)

 Introducing a tail reference, that points to the last node

will make the process more efficient.
class MyLinkedList{
Node head;
 insertLast() and insertFirst()
Node tail; methods need to be revised to
int size; accommodate the tail
MyLinkedList(){
head = null;
tail = null;
size = 0;
}
}

Compiled & edited by: Zahid Zainal

 Improving Linked List (cont.)

public void insertFirst(int x) { public void insertLast (int x) {

Node newNode = new Node(); if (head == null)
newNode.data = x; insertFirst(x);
newNode.next = head; else {
head = newNode; Node newNode = new Node();
if (tail == null) newNode.data = x;
tail = head; newNode.next = null; Link the last node to
size++; the new node added
} tail.next = newNode; into the list
tail = newNode;

size++; Update tail to point

Case when a node is to the new last node
added into an empty list }
}

No traversing needed.
Compiled & edited by: Zahid Zainal
 Improving Linked List (cont.)

 Tail does not improve removeLast() operation.

 How about if we want to display the element in reverse?
Higher time
 Use nested loop complexity
Higher space
 Use recursion complexity

 Efficiency of accessing element at specific index depends

on the size of the linked list.

How can we
improve?

Compiled & edited by: Zahid Zainal

 Reverse Print

First loop to set the

 Nested Loop limit in decreasing order  Recursion stop recursion if we
reach list end

public void printReverse(){ public void printReversell(){

for(int limit = size-1; limit>=0; printRecursive(head);
limit--){ }
Node temp = head; public void printRecursive(Node temp){
for(int i= 0; i<limit; i++) { if(temp != null) { print remaining
temp = temp.next; printRecursive(temp.next); items first
System.out.println(temp.data); System.out.println(temp.data);
} }
} }
}
Second loop to traverse
the list and display

then print
current item
Compiled & edited by: Zahid Zainal
 Doubly Linked List

 A linked list where every node has access to the next and
previous node.
 has a next reference variable and a back reference variable
 contains the address of the next node (except the last node)
 contains the address of the previous node (except the first node)
 Traversal can happened in both direction

Compiled & edited by: Zahid Zainal

 Doubly Linked List Operation

 Node definition  Insert at the beginning

class Node{ public void doublyInsertFirst(int x) {
int data; Node newNode = new Node();
Node next; newNode.data = x; prev for first node is
Node prev; newNode.next = head; always null
} newNode.prev = null;
head = newNode;
case on insert into an
if (tail == null)
empty list tail = head;
else
newNode.next.prev = newNode;
size++;
}
Update prev of former first
node to point to the new
first node
Compiled & edited by: Zahid Zainal
 Doubly Linked List Operation (cont.)

Traversing from the

end of the list
 Insert at the beginning  Reverse print
public void insertLast (int x) { public void reversePrint () {
Node newNode= new Node(); Node temp = tail;
newNode.data = x; while (temp != null) {
newNode.next = null; System.out.println(temp.data);
newNode.prev = tail; temp = temp.prev;
tail = newNode; }
if (head == null) }
case on insert into an
head = newNode; empty list
else
newNode.prev.next = newNode;
size++;
}

Compiled & edited by: Zahid Zainal

 Doubly Linked List Operation (cont.)

Write you own

methods for

Removing node from

double link list???

Compiled & edited by: Zahid Zainal

 Notes on Doubly Linked Lists

 The main advantage of Doubly Linked Lists is to efficiently

traverse list nodes in both directions
 Applications: to implement back and forward buttons in a web
browser, undo and redo actions, etc.
 We can also use two-way traversal to reduce time
required to reach an item at a given index
 if index <= size/2, start from head and move forward
 otherwise, start at tail and move backward
 on average, would make insertItemAt(), deleteItemAt(),
getItemAt() and setItemAt() 2 times faster

Compiled & edited by: Zahid Zainal

 Circular Linked List

 Some problems are inherently circular (squares on a

Monopoly board), and many solutions can be solved more
naturally using a circular data structure (round robin
scheduling, players taking turns, playing video and sound
files in “looping” mode, etc.)
 A linked list is made circular if its end points to its
beginning, i.e. the last node points to the first one
 Circular traversal is made more natural, rather than always testing
if we have reached to the end and starting over

Compiled & edited by: Zahid Zainal

 Circular Linked List Characteristics

 Data representation for a Circular Linked List is not

different from the normal Linked List
 The concept is just not to store NULL at the link field of last node,
and respect that in implementing all operations
 Often, tail pointer is only used instead of head

Compiled & edited by: Zahid Zainal

 Circular Linked List Operation

 Insert at the beginning of the list

public void insertAtBeginning(int x){
Node newNode= new Node();
newNode.data = x;
if (tail == null
tail = newNode; newNode
tail.next = tail;
}
else{ X
newNode.next = tail.next;
tail.next = newNode; 4
} newNode
size++;
}

Compiled & edited by: Zahid Zainal

 Circular Linked List Operation (cont.)

 Print circular linked list

public void print(){

if(tail != null){
Node Temp = tail.next;
do{
System.out.println(temp.data);
temp = temp.next;
}while (temp != tail.next);
}
}

Compiled & edited by: Zahid Zainal

 Multidimensional Linked List

Compiled & edited by: Zahid Zainal

 Array or Linked List?

 Finally, should we always use linked lists?

 Decision depends on what operations will be used most
frequently, and which factors (speed/memory) are more
critical. Following are some hints:
 Number of elements is known: use array
 Dynamic addition and expansion: linked list
 Deletion at any position: linked list
 Need lots of random access: use array
 Searching and items are unsorted: both same
 Searching and items are sorted: array (binary search)
 Sorting using bubble sort: both same
 Sorting using other methods: depends on the method
Compiled & edited by: Zahid Zainal
 Summary

 Improvement of insertLast() method.

 Variation of linked list
 Doubly linked list
 Circular linked list
 Multidimensional linked list

Compiled & edited by: Zahid Zainal

 Next Topic…

 Stack
 Concept
 Application
 Implementation

Compiled & edited by: Zahid Zainal

 References

 Carrano, F. & Savitch, W. 2005. Data Structures and

Abstractions with Java, 2nd ed. Prentice-Hall.
 Malik D.S, & Nair P.S., Data Structures Using Java,
Thomson Course Technology, 2003.
 Rada Mihalcea, CSCE 3110 Data Structures and Algorithm
Analysis notes, U of North Texas.

Compiled & edited by: Zahid Zainal