lecture

function removeLast(): # DLinkedList with trailer
if size = 0:
error!
lastElem = tail.prev

lastElem.prev.next = lastElem.next # or, tail
lastElem.next.prev = lastElem.prev
size--


function removeLast(): # DLinkedList without trailer
if size = 0:
error!
else if size = 1:
head = tail = null
size--
else:
tail = tail.prev
tail.next = null
size--


function insertFront(elem x): # DLinkedList with header
n = new Node(x)
oldFirstNode = head.next

head.next = n
n.prev = head

oldFirstNode.prev = n
n.next = oldFirstNode
size++
/*
# their way, v being the new node n
w = head.next
v.next = w
v.prev = head
w.prev = v
head.next = v
size++
*/

function insertFront(elem x): # DLinkedList without header and trailer
n = new Node(x)

if size = 0:
head = tail = n
else:
n.next = head
head = n
n.prev = null
n.next.prev = n
size++


An "interesting" situation. We have DNodes and Dlists.
DNodes have getNext() and getPrev()
DLists have getNext(DNode n) and getPrev(DNode n)

procedure based
DNode getPrev(Dnode n)
{

}

object oriented programming
n.getPrev()

lecture

HW: modify the stack class, such that when you reach the capacity, it increases in size.

time the pushing of elements.
start by inserting, say 50.
100
200
300
400
500

until 1000.
play around to find a good magnitude

based on this, push is O(what)?

________________________

how do i traverse the linked list?
for (Node current = head; current != null; current = current.next)
;// do something with the current node


function printFirstToLast(Node here):
if here = null:
return
else:
# do something
print here.element
printFirstToLast(here.next)

HW: write a recursive printLastToFirst(Node here):
write an iterative printLastToFirst(Node here):
If you can, figure out what the recursive and iterative implementations are O of.


How do we insert at the start?

function insertAtStart(value x):
n = new Node()
n.element = x
n.next = head
head = n
size++

function insertAtEnd(value x):
# first, create the new node
n = new Node()
n.element = x
n.next = null

# then, find the last node in the list
for(current = head; current.next != null; current = current.next)
; # do nothing

# now, current in the end of the list
current.next = n
size++

function insertAtEnd(value x): # this time, with a tail
# first, create the new node
n = new Node()
n.element = x
n.next = null

# then, add to the end of the list
tail.next = n

# then, update the tail
tail = n
size++


function insertBefore(element x, Node v):
# find the node immediately before v
for (curr=head; curr.next!=v; curr=curr.next)
; # do nothing

# create a node
n = new Node()
n.element = x

# put it in the list in proper place
# recall that curr in the node before v
curr.next = n
n.next = v


function insertBeforeValue(element x, value v):
for (curr=head; curr.element!=v; prev=curr, curr=curr.next):
; # do nothing
# now, curr is the node with element v in it

# new node
n = new Node()
n.element = x

#put n in its proper place
n.next = curr
prev.next = n

hw: into the string data type, add a method
called insert(string s, int pos)
which will insert s into position pos in your
MyString type.

hw:
write a string class
based on an array of chars
methods:
len
get
set
append

some notes

class MutableString
{
private String data;
String toString() { return data; }
setValue(String x) { data = x; }
String getValue() { return data; }
}


Swap(MutableString a, MutableString b)
{
MutableString t = new MutableString;
t.setValue(a.getValue()); // c = a
a.setValue(b.getValue()); // a = b
b.setValue(t.getValue()); // b = t
}

String a = "hello";
String b = "hi";
if (a.equals(b))
{

}
String s = "";
for (int i = 0; i < 100; i++)
{
s += i;
s += "\n";
}


String s = new String("");
for (int i = 0; i < 100; i++)
{
s += new Integer(i).toString();
}

more hw

HW #2:

Adapt your C++ stack class into a Java class.

class Stack
{
int A[] = new int[100];
//...

Due: next Thurs


HW:3
Show that 2n - 5 is O(n)
Due: next Thurs

Slides now up

on Blackboard, under course documents.

lecture 2 notes

HW #1: Make a C++ Stack class. It should hold ints. We should have the following methods: empty, full, push, pop, top. It should be based on an array.

class Stack
{
int A[100];
int Top;
public:
Stack() { }
void push(int x) { A[Top++] = x; }
int pop() { return A[--Top]; }
int top() { return A[Top-1]; }
bool isEmpty() { ... }
bool isFull() { ... }
}

main()
{
Stack a;
a.push(6);
...
return 0;
}

Person p   =   new Person("John");
// is the same as
Person p;
p   =   new Person("John");