DS4 LISTS

Question 1

LISTS GENERAL

Answer 1

-dynamic size easy add-remove
-start and end
-non serially stored in memory
-cannot access item randomly must parse the list
-node contains data and pointers to other node(s)
types:
-single linked (node points to the next node)
-double linked (node points to previous and next node)
-single and double linked circular (end points to beginning)

Question 2

SINGLE LINKED LIST

Answer 2

node contains data and the next node
self-referent
stream of items

class Node
{
~Object item;
~Node next;
~Node(Object v){
~~item = v;
~~next = null;}
}

Question 2

SINGLE LINKED LIST INTERNAL REMOVE

Answer 2

removing :
we must know the previous object prev
Node t = prev.next;
prev.next = t.next; // set the previous node’s next field to the next of the node we want to delete
other way: prev.next = prev.next.next;

!! different when remove is at head or tail of the list

Question 3

SINGLE LINKED LIST INTERNAL INSERT

Answer 3

inserting:
we must know the node that is gonna be before (prev) the inserted node t
t.next = prev.next; //set the next field as prev.next so we dont lose the rest of the list
prev.next = t; // connect t to the list

!! different when insert is at head or tail of the list

Question 4

SINGLE LINKED LIST GET NODE N

Answer 4

getting node n:
Node x = head;
for (int i = 1 ; i<n; i++)
{if(x.next != null){x = x.next;}}

Question 5

LIST VS ARRAY

Answer 5

list is dynamic in size but requires at least double storage than a static array with same number of items in it

insert and remove is O(n) in array but O(1) in list

getting item k is O(1) in array thanks to indexing but O(n) in list

Question 6

LIST INVERT

Answer 6

input: head
output: list obj with reversed order
idea is to preserve 3 pointers to previous current and next nodes

Node next;
Node current = x;
Node previous;
while(current != null){
next = current.next; //keep next node since we are going to replace it with the previous one
current.next = previous; //reversing previous and next
//step to the next iteration
previous = current;
current = next;
}return previous;// this is the new head of the list

Question 7

LIST INSERTION SORT

Answer 7

input: integers
output: sorted list
idea:
pseudo-node head is not used
list a store unsorted inputs
list b sorted
iterate a
get item remove it put it in the correct place in b

import java.util.Scanner;
class ListSort{
~static class Node{
~~int val;
~~Node next = null;
~~Node(int v, Node t){val = v; next= t;}
~}

~void print(Node h){
~~for(Node t = h.next; t != null; t= t.next){
~~~System.out.println(t.val);
~~}
~}
~static Node sort(Node a){
~~Node b = new Node(0, null);
~~Node curr, u, x;
~~while(a.next != null){
~~~//delete curr from a
~~~curr = a.next;
~~~u = curr.next;
~~~a.next = u;
~~~//sort start
~~~x = b;
~~~while (x.next != null && x.next.val < curr.val) {
~~~~x = x.next;
~~~}
~~~curr.next = x.next;
~~~x.next = curr;

~~}

~~return b;
~}
~public static void main(String[] args){
~ListSort l = new ListSort();
~Node a = new Node(0, null);
~Scanner In = new Scanner(System.in);
~for(int i = 0; i<6 ;i++){

~~a.next = new Node(In.nextInt(),a.next);

~}
~l.print(a);
~Node b = sort(a);
~l.print(b);

~In.close();
~}
}

we can do it with 1 list but sometimes we need a create() method to read input
complexity is O(n^2)

Question 8

CIRCULAR LIST JOSEPHUS PROBLEM

Answer 8

n people in a circle
we remove person m
from person m+1 we do the same until 1 person is left

n node circular list
iterate m times then delete object set current to the next of the one deleted and loop
do until curr.next ==curr

Question 9

ARRAY JOSEPHUS PROBLEM

Answer 9

it is possible to implement lists with the use of arrays
we need 2 arrays 1 for value[] and 1 for next[]
remove is next[x] = next[next[x]]

Question 10

HEAD TAIL CONVENTIONS

Answer 10

-circ list is never empty always has head and points to itself
-single linked that doesnt have pseudo head needs special insertion and remove methods for head
-with pseudo head no need for special methods and list always has at least 1 node
-both pseudo head and tail list has 2nodes upon creation

Question 11

DOUBLE LINKED LIST

Answer 11

is similar to single linked but has one more pointer to previous node
is costlier to update and store
but easier to insert remove since we have access to previous node