Khulna University, Khulna

Computer Science and Engineering Discipline

Course No: CSE 2102
Course Title: Data Structures Laboratory
Problem Set: Linked List

Singly Linked Lists

1. Write a Count(item ) method that counts the number of times a given int (item)
occurs in a list.

2. Write a GetNth(index ) method that takes an integer index and returns the data
value stored in the node at that index position. GetNth() uses the C numbering
convention that the first node is index 0, the second is index 1, . . . and so on.
So for the list 42, 13, 666 GetNth(1) with index 1 should return 13. The index
should be in the range [0..length-1]. If it is not, the method should warn the user.

3. Write a method Delete(item) that deletes all occurences of item in the list.

4. Write a method InsertNth(index ) which can insert a new node at any index
within a list. The caller may specify any index in the range [0..length], and the
new node should be inserted so as to be at that index.

5. Write an InsertSort() method which rearranges its nodes so they are sorted in
increasing order.

6. Write an Append() method that takes a list and appends ’b’ onto the end of ’a’
for the statement [Link](b).

7. Given a list, split it into two sublists one for the front half, and one for the back
half. If the number of elements is odd, the extra element should go in the front
list. So FrontBackSplit() on the list {2, 3, 5, 7, 11} should yield the two lists
{2, 3, 5} and {7, 11}.
Hint. compute the length of the list, then use a for loop to hop over the right
number of nodes to find the last node of the front half, and then cut the list at
that point. There is a trick technique that uses two pointers to traverse the list.
A “slow” pointer advances one nodes at a time, while the “fast” pointer goes two
nodes at a time. When the fast pointer reaches the end, the slow pointer will be
about half way. For either strategy, care is required to split the list at the right
point.

8. Write a RemoveDuplicates() method which deletes any duplicate nodes from

the list. Ideally, the list should only be traversed once.

9. Write a method SwapNode(a, b) takes two indexes a and b, and swaps the con-
tents of a and b.

10. Write a method AlternatingSplit() that takes one list and divides up its nodes
to make two smaller lists. The sublists should be made from alternating elements
in the original list. So if the original list is {a, b, a, b, a}, then one sublist should
be {a, a, a} and the other should be {b, b}.

11. Given two lists, merge their nodes together to make one list, taking nodes alter-
nately between the two lists. So [Link](bList ) with {1, 2, 3}
and {7, 13, 1} should yield {1, 7, 2, 13, 3, 1}. If either list runs out, all the nodes
should be taken from the other list.

1
12. Write a method insertAfter(item1, item2) which inserts a node with item2
after the first occurence of item1 in the list.

13. Problem 4 in problem set 03 could handle a maximum of only 500 entries. Using
linked lists, redo the program to handle as many entries as required. Add the
following operations to your program:

a. Add or delete a new entry to the address book.

b. When the program terminates, write the data in the address book to a disk.

14. Extend the class linkedListType by adding the following operations:

a. Find and delete the node with the smallest info in the list. (Delete only the
first occurrence and traverse the list only once.)
b. Find and delete all occurrences of a given info from the list. (Traverse the
list only once.)

Add these methods to the class unorderedLinkedList. Also write a program to

test these functions.

15. (Splitting a linked list, at a given node, into two sublists)

1. Add the following operation to the class linkedListType:

1 // D i v i d e t h e l i s t a t t h e node with t h e i n f o item i n t o two
sublists .
2 // P o s t c o n d i t i o n : f i r s t and l a s t p o i n t t o t h e f i r s t and l a s t
3 // nodes o f t h e f i r s t s u b l i s t .
4 // s e c o n d L i s t . f i r s t and s e c o n d L i s t . l a s t p o i n t t o t h e
5 // f i r s t and l a s t nodes o f t h e s e c o n d s u b l i s t .
6 p u b l i c v o i d d i v i d e A t ( LinkedListType<Type> s e c o n d L i s t , E item )
7 {
8 ......
9 }

Consider the following statements:

UnorderedLinkedList<Integer> myList;
UnorderedLinkedList<Integer> otherList;
Suppose myList points to the list with the elements:
34 65 18 39 27 89 12
(in this order). The statement:
[Link](otherList, 18); divides myList into two sublists: myList
points to the list with the elements 34 65, and otherList points to the sub-
list with the elements
18 39 27 89 12.
2. Write the definition of the method to implement the operation divideAt.
Also write a program to test your method.

16. Add the following operation to the class OrderedLinkedList:

1 // D i v i d e t h e l i s t a t t h e node with t h e i n f o item i n t o two s u b l i s t s .

2 // P o s t c o n d i t i o n : f i r s t and l a s t p o i n t t o t h e f i r s t and l a s t
3 // nodes o f t h e f i r s t s u b l i s t .
4 // s e c o n d L i s t . f i r s t and s e c o n d L i s t . l a s t p o i n t t o t h e
5 // f i r s t and l a s t nodes o f t h e s e c o n d s u b l i s t .
6 p u b l i c v o i d d i v i d e A t ( LinkedListType<Type> s e c o n d L i s t , E item )
7 {
8 ......
9 }

Example: Consider the following statements:

OrderedLinkedList<Integer> newList;
OrderedLinkedList<Integer> list1;
OrderedLinkedList<Integer> list2;

Page 2
 Suppose list1 points to the list with the elements 2 6 7 and list2 points to the
list with the elements 3 5 8. The statement:
[Link](list1, list2); creates a new linked list with the ele-
ments in the order 2 3 5 6 7 8 and the object newList points to this list. Also,
after the preceding statement executes, list1 and list2 are empty.
Write the definition of the method mergeLists to implement the operation merge-
Lists. Also write a program to test your function.

17. The function insert of the class OrderedLinkedList does not check if the item
to be inserted is already in the list; that is, it does not check for duplicates.
Rewrite the definition of the method insert so that before inserting the item it
checks whether the item to be inserted is already in the list. If the item to be
inserted is already in the list, the method outputs an appropriate error message.
Also write a program to test your method.

18. Extend the class LinkedListType by adding the following function:

1 // Method t o remove t h e f i r s t node o f a l i n k e d l i s t and put i t
2 // a t t h e end o f t h e l i n k e d l i s t .
3 public void r o t a t e ( )
4 {
5 .......
6 }

19. Write a program that prompts the user to input a string and then outputs the
string in the pig Latin form. The rules for converting a string into pig Latin form
are as follows:

a. If the string begins with a vowel, add the string “-way” at the end of the
string. For example, the pig Latin form of the string “eye” is “eye-way”.
b. If the string does not begin with a vowel, first add “-” at the end of the
string. Then rotate the string one character at a time; that is, move the first
character of the string to the end of the string until the first character of the
string becomes a vowel. Then add the string “ay” at the end. For example,
the pig Latin form of the string “There” is “ere-Thay”.
c. Strings such as “by” contain no vowels. In cases like this, the letter y can
be considered a vowel. So, for this program the vowels are a, e, i, o, u, y, A,
E, I, O, U, and Y. Therefore, the pig Latin form of “by” is “y-bay”.
d. Strings such as “1234” contain no vowels. The pig Latin form of the string
“1234” is “1234-way”. That is, the pig Latin form of a string that has no
vowels in it is the string followed by the string “-way”.

Your program must store the characters of a string into a linked list and use the
method rotate, as described in previous question, to rotate the string.

20. Write a method hasSpecial() which returns true if there exists two unique
numbers in the list that sum to a third number in the list.
Doubly Linked List
1. Give an algorithm (and a program) for concatenating two doubly linked lists L
and M, with header and trailer sentinel nodes, into a single list L.

2. Implement the clone() method for the DoublyLinkedList class.

3. Write the definitions of the method copyList for the class DoublyLinkedList.

4. In Java, an integer type allows 232 different integer values, from -2,147,483,648
to 2,147,483,647 and a long type allows 264 different integer values, from -
9,223,372,036,854,775,808 to 9,223,372,036,854,775,807. Write a program using
doubly linked list to add two long integers (having more than 26 digits) from an
input file.
Sample input and output:

Page 3
 Input: 354224848179261915075
573147844013817084101
========================
Output: 927372692193078999176

Outline:

a. Make two doubly linked lists from the three input long integers
b. If the two numbers are not of the same length insert ’0’ in front of the small
integer
c. Then traverse to the end of the two input and start adding digit by digit
from the last digits towards the first digit and make another list for the
result
d. Print out the result

Circular Linked List

1. Suppose you are given two circularly linked lists, L and M.

2. Describe an algorithm (and a program) for telling if L and M store the same
sequence of elements (but perhaps with different starting points).

3. Implement the clone() method for the CircularlyLinkedList class.

4. In the Jewish revolt against Rome, Josephus and 39 of his comrades were holding
out against the Romans in a cave. With defeat imminent, they resolved that,
like the rebels at Masada, they would rather die than be slaves to the Romans.
They decided to arrange themselves in a circle. One man was designated as
number one, and they proceeded clockwise killing every seventh man. Josephus
(according to the story) was among other things an accomplished mathematician;
so he instantly figured out where he ought to sit in order to be the last to go.
But when the time came, instead of killing himself he joined the Roman side.
Write a program that will determine the sequence of execution of the comrades,
i.e., the last man to survive. Your program will take three inputs:

1. n the number of comrades

2. n comrades as A, B, C, D .....
3. k is the number determining which comrade is to execute next

Note: First time the counting will start at position 0.

Sample input:
n=8
D, A, R, S, T, J, L, M
k=3
Sample output:
Execution sequence: R, J, D, T, A, M, S
Survivor: L

Page 4