Data Structure Course 1) After reviewing the Java implementation of the double l
ID: 3749860 • Letter: D
Question
Data Structure Course
1) After reviewing the Java implementation of the double linked list you will write a Java program that will swap the first and last element.
2) Implement the pop and push methods of a stack using a) an ArrayList and b) an Array. Explain the major differences.
3) Implement an algorithm to sort elements of the queue in increasing order. What is the worst, average and best case complexity of the algorithm?
input : front [11, 23, -27, 14, -1, 8, 0, 12, -10, 3] back
output: front [ -27, -10, -1, 0, 3, 8, 11, 12, 14, 23] back
Explanation / Answer
1) Please find the function below to swap the first and last element in the linked list.
CODE
====================
class Node
{
protected int data;
protected Node next, prev;
/* Constructor */
public Node()
{
next = null;
prev = null;
data = 0;
}
/* Constructor */
public Node(int d, Node n, Node p)
{
data = d;
next = n;
prev = p;
}
/* Function to set link to next node */
public void setLinkNext(Node n)
{
next = n;
}
/* Function to set link to previous node */
public void setLinkPrev(Node p)
{
prev = p;
}
/* Funtion to get link to next node */
public Node getLinkNext()
{
return next;
}
/* Function to get link to previous node */
public Node getLinkPrev()
{
return prev;
}
/* Function to set data to node */
public void setData(int d)
{
data = d;
}
/* Function to get data from node */
public int getData()
{
return data;
}
}
/* Class linkedList */
class linkedList
{
protected Node start;
protected Node end ;
public int size;
/* Constructor */
public linkedList()
{
start = null;
end = null;
size = 0;
}
/* Function to check if list is empty */
public boolean isEmpty()
{
return start == null;
}
/* Function to get size of list */
public int getSize()
{
return size;
}
/* Function to insert element at begining */
public void insertAtStart(int val)
{
Node nptr = new Node(val, null, null);
if(start == null)
{
start = nptr;
end = start;
}
else
{
start.setLinkPrev(nptr);
nptr.setLinkNext(start);
start = nptr;
}
size++;
}
/* Function to insert element at end */
public void insertAtEnd(int val)
{
Node nptr = new Node(val, null, null);
if(start == null)
{
start = nptr;
end = start;
}
else
{
nptr.setLinkPrev(end);
end.setLinkNext(nptr);
end = nptr;
}
size++;
}
/* Function to insert element at position */
public void insertAtPos(int val , int pos)
{
Node nptr = new Node(val, null, null);
if (pos == 1)
{
insertAtStart(val);
return;
}
Node ptr = start;
for (int i = 2; i <= size; i++)
{
if (i == pos)
{
Node tmp = ptr.getLinkNext();
ptr.setLinkNext(nptr);
nptr.setLinkPrev(ptr);
nptr.setLinkNext(tmp);
tmp.setLinkPrev(nptr);
}
ptr = ptr.getLinkNext();
}
size++ ;
}
/* Function to delete node at position */
public void deleteAtPos(int pos)
{
if (pos == 1)
{
if (size == 1)
{
start = null;
end = null;
size = 0;
return;
}
start = start.getLinkNext();
start.setLinkPrev(null);
size--;
return ;
}
if (pos == size)
{
end = end.getLinkPrev();
end.setLinkNext(null);
size-- ;
}
Node ptr = start.getLinkNext();
for (int i = 2; i <= size; i++)
{
if (i == pos)
{
Node p = ptr.getLinkPrev();
Node n = ptr.getLinkNext();
p.setLinkNext(n);
n.setLinkPrev(p);
size-- ;
return;
}
ptr = ptr.getLinkNext();
}
}
public void swapFirstWithLast() {
Node temp = end;
end.next = start.next;
end.prev = null;
start.next.prev = end;
end = start;
start.next = null;
start.prev = temp.prev;
temp.prev.next = start;
end = temp;
}
}
2) Please find the implementation of Stack using
a) an ArrayList:
class StackUsingArrayList {
private ArrayList<Integer> stack = new ArrayList<>();
public void push(int item) {
stack.add(item);
}
public int pop() {
// Return and remove the top item from
// the stack.
if (stack.isEmpty())
return 0-1;
return stack.remove(stack.size()-1);
}
public boolean isEmpty() {
return stack.isEmpty();
}
}
b) an Array:
class StackUsingArray {
private int stack[];
private int size;
private int index = 0;
public StackUsingArray(int size) {
this.size = size;
stack = new int[size];
}
public void push(int element) {
if (isFull()) {
System.out.println("Stack is already full!!");
}
stack[index] = element;
index++;
}
public int pop() {
if (isEmpty()) {
return -1;
}
return stack[--index];
}
public boolean isEmpty() {
if (index == 0) {
return true;
}
return false;
}
public boolean isFull() {
if (index == size) {
return true;
}
return false;
}
}
DIFFERENCE:
3) Please find the code below.
CODE
====================
// Java program to implement sorting a
// queue data structure
import java.util.LinkedList;
import java.util.Queue;
class GFG
{
// Queue elements after sortIndex are
// already sorted. This function returns
// index of minimum element from front to
// sortIndex
public static int minIndex(Queue<Integer> list,
int sortIndex)
{
int min_index = -1;
int min_value = Integer.MAX_VALUE;
int s = list.size();
for (int i = 0; i < s; i++)
{
int current = list.peek();
// This is dequeue() in Java STL
list.poll();
// we add the condition i <= sortIndex
// because we don't want to traverse
// on the sorted part of the queue,
// which is the right part.
if (current <= min_value && i <= sortIndex)
{
min_index = i;
min_value = current;
}
list.add(current);
}
return min_index;
}
// Moves given minimum element
// to rear of queue
public static void insertMinToRear(Queue<Integer> list,
int min_index)
{
int min_value = 0;
int s = list.size();
for (int i = 0; i < s; i++)
{
int current = list.peek();
list.poll();
if (i != min_index)
list.add(current);
else
min_value = current;
}
list.add(min_value);
}
public static void sortQueue(Queue<Integer> list)
{
for(int i = 1; i <= list.size(); i++)
{
int min_index = minIndex(list,list.size() - i);
insertMinToRear(list, min_index);
}
}
//Driver function
public static void main (String[] args)
{
Queue<Integer> list = new LinkedList<Integer>();
list.add(30);
list.add(11);
list.add(15);
list.add(4);
//Sort Queue
sortQueue(list);
//print sorted Queue
while(list.isEmpty()== false)
{
System.out.print(list.peek() + " ");
list.poll();
}
}
}
Best-case Time complexity: O(n2)
Average-case Time complexity: O(n2)
Worst-case Time complexity: O(n2) []
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.