[go: up one dir, main page]
Scribd
Upload
27 views29 pages

Linked List (Part2)

The document discusses different operations for singly linked lists including searching, traversing, retrieving nodes, and destroying lists. It then describes implementing these operations for circular linked lists which connect the last node to the first node to allow for cyclic traversal. Circular linked lists provide an efficient implementation for round-robin scheduling by removing the need to explicitly track the head of the list.

Uploaded by

pilotbairexd
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
27 views29 pages

Linked List (Part2)

The document discusses different operations for singly linked lists including searching, traversing, retrieving nodes, and destroying lists. It then describes implementing these operations for circular linked lists which connect the last node to the first node to allow for cyclic traversal. Circular linked lists provide an efficient implementation for round-robin scheduling by removing the need to explicitly track the head of the list.

Uploaded by

pilotbairexd
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
You are on page 1/ 29

CS 242 -

Data Structures
Linked lists – Part 2

1
Singly Linked List ADT-Extra operation
 Search List
 Traverse List
 Retrieve Node
 Destroy List

2
Singly Linked List ADT-Extra operation
Search List
Locating specific data in a list.
In linked list we use sequential search.
We need a key field for search operation.

Traverse List
Start with the head and access each node until you reach null.
Do not change the head reference.

3
Singly Linked List ADT-Extra operation

Retrieve Element
By using search method.

Destroy List
Deletes all nodes still in the list.
It then sets the metadata to a null list condition

4
Singly Linked List ADT: Extra methods

 Traverse the list by Curr reference (helper methods)


next(): change Curr position to the next node.
moveToStart(): change Curr position to the first of list.
moveToEnd(): change Curr position to the end of list.
moveToPos(pos): move Curr to specific position(pos)
CurrPos(): return the position (index) of Curr.
getValue(): return the element of Curr reference.

5
Singly linked list implementation:
helper methods

6
Singly linked list implementation:
helper methods

7
Singly linked list implementation:
helper methods

8
Comparison of List Implementations

9
Linked List

Advantages
Data easily inserted and deleted
No need to shift elements of LL to make room for a new
element or to delete an element
Disadvantages
We are limited to a sequential search

10
Circularly Linked Lists

Many applications in which data can be more naturally viewed as


having a cyclic order with well-defined neighboring
relationships, but no fixed beginning or end
Multiplayer games
City buses
Operating system

11
Round-robin scheduling

A process is given a short turn to execute, known as a time slice


The slice ends and the job is complete.
The slice ends and the job is not yet complete.
A traditional linked list, by repeatedly performing the following
steps on linked list L
1. process p = L.removeFirst( )
2. Give a time slice to process p
3. L.addLast(p)

12
Round-robin scheduling

Drawbacks to the use of a traditional linked list


Inefficient to remove a node from one end of the list and then create a
new node for the same element.
Decrement and increment the list’s size
Unlink and relink nodes

Can we build a more efficient data structure for representing a


cyclic order
A modification to our singly linked list implementation

13
Circularly linked list

 A singularly linked list in which the next reference of


the tail node is set to refer back to the head of the list
(rather than null)

14
Circularly linked list

Supports all the public methods of our SinglyLinkedListclass


One additional update method rotate( )
Moves the first element to the end of the list.

15
CircularlyLinkedList class
 Round-robin scheduling can be efficiently implemented by
repeatedly performing the following steps on a circularly
linked list C
1. Give a time slice to process C.first( )
2. C.rotate( )

 Additional optimization
 We no longer explicitly maintain the head reference
 We can locate the head as tail.getNext( )

16
CircularlyLinkedList

17
CircularlyLinkedList

18
CircularlyLinkedList

tail

X Y Z

tail

Y Z X

19
CircularlyLinkedList (addFirst)

 Empty list:
tail
A

20
CircularlyLinkedList (addFirst)

 Nonempty list:
tail

X Y Z
newest

21
CircularlyLinkedList (addFirst)

 Nonempty list:
tail

A X Y Z
newest

22
CircularlyLinkedList (addFirst)

 Nonempty list:
tail

A X Y Z
newest

23
CircularlyLinkedList (addLast)

tail

X Y Z
tail

A X Y Z
tail

A X Y Z
tail

X Y Z A
24
CircularlyLinkedList (removeFirst)

 Empty list: tail

25
CircularlyLinkedList (removeFirst)

 List with only one node:


head tail

26
CircularlyLinkedList (removeFirst)

 List with only one node:


head tail

27
CircularlyLinkedList (removeFirst)

 List with more than one node:


head tail

X Y Z

28
CircularlyLinkedList (removeFirst)

 List with more than one node:


head tail

X Y Z

29

You might also like