Link List & their Operations-Data Structure

Link List

1. 10/20/24 1
List Operations
15-111
Advanced Programming
Ananda Gunawardena

2. 10/20/24 2
Advantages of Linked Lists
•The advantages of linked lists include:
–Overflow can never occur unless the memory
is actually full.
–Insertions and deletions are easier than for
contiguous (array) lists.
–With large records, moving pointers is easier
and faster than moving the items themselves.

3. 10/20/24 3
Disadvantage of Linked Lists
•The disadvantages of linked lists include:
–The pointers require extra space.
–Linked lists do not allow random access.
–Time must be spent traversing and changing
the pointers.
–Programming is typically trickier with pointers.

4. 10/20/24 4
Linked List Operations

5. 10/20/24 5
List Operations
•Basic Operations on a Linked List are
–Insertion
–Deletion
•Other operations include
– build list
–Append and prepend (special cases of insert)
–empty
–length
–toString
–traversing

6. 10/20/24 6
List Traversal
head
null

7. 10/20/24 7
Insertion
•Two cases to consider
–List is empty
•Insert to the beginning of the list
–List is non-empty
•Locate the place to insert
•Manipulate the references to make new links
head

8. 10/20/24 8
Insert Operation
P
New node

9. 10/20/24 9
Delete Operation
P
Node

10. 10/20/24 10
Other Operations

11. 10/20/24 11
Prepend
head
New node
Insert to the beginning of the list
null

12. 10/20/24 12
Append
head
New node
Insert to the end of the list
null

13. 10/20/24 13
Length
head
Insert to the end of the list
null

14. 10/20/24 14
List Types

15. 10/20/24 15
Doubly Linked Lists
•Typically a linked list with two pointers (next and
previous) is called a doubly linked list
class Node {
Object data;
Node next;
Node previous;
…..
}
head

16. 10/20/24 16
Inserting into a Doubly Linked List
•We have to manipulate both next and
previous pointers. Insert new node N
between P and Q
Node P Node Q Node R
Node N

17. 10/20/24 17
Deleting from a Doubly Linked List
•Write the code to delete Node Q
Node P Node Q Node R

18. 10/20/24 18
Building a Doubly Linked List
•Build a doubly linked list with 3 nodes (always insert to the front of the list)
•Node Head = new Node(new Integer(3), null, null);
•Node N = new Node(new Integer(4), null, null);
•Connect the two nodes
•Insert the next node to the list

19. 10/20/24 19
Make it a Circular Doubly Linked
List
•Write the code to create a circular doubly
linked list.

20. 10/20/24 20
Multi Linked List - An
Example