programing java

 

The classes ListNode and StringLinkedList are given in the lecture slides 18 attached.  Write your demo program that tests the methods in those classes.

•      

Create a linked list

•       Add the courses you took into the linked list

•       Check whether CSCI185 is in the list or not

•       Show all courses in the linked list

•       Delete the first course you added

•       Show all courses after deleting the first course

Lecture 18
Dynamic Data Structures and Generics (II)
*

*

Class ArrayList
Object of an ArrayList can be used to store an unlimited number of objects.
*

Methods of ArrayList (I)
*

java.util.ArrayList

+ArrayList()

+add(o: Object) : void

+add(index: int, o: Object) : void

+clear(): void

+contains(o: Object): boolean

+get(index: int) : Object

+indexOf(o: Object) : int

+isEmpty(): boolean

+lastIndexOf(o: Object) : int

+remove(o: Object): boolean

+size(): int

+remove(index: int) : Object

+set(index: int, o: Object) : Object

Appends a new element o at the end of this list.

Adds a new element o at the specified index in this list.

Removes all the elements from this list.

Returns true if this list contains the element o.

Returns the element from this list at the specified index.

Returns the index of the first matching element in this list.

Returns true if this list contains no elements.

Returns the index of the last matching element in this list.

Removes the element o from this list.

Returns the number of elements in this list.

Removes the element at the specified index.

Sets the element at the specified index.

Creates an empty list.

Methods of ArrayList (II)
Array is used to implement the methods
Methods get(int index) and set(int index, Object o) for accessing and modifying an element through an index and the add(Object o) for adding an element at the end of the list are efficient. Why?
Methods add(int index, Object o) and remove(int index) are inefficient because it requires shifting potentially a large number of elements.
*

Linked Data Structure
To improve efficiency for adding and removing an element anywhere in a list.
It contains
Collection of objects
Each object contains data and a reference to another object in the collection
*

Linked List
A dynamic data structure
A linked list consists of nodes. Each node contains
an element
a link: linked to its next neighbor.
Example: take notes in the class!
*

Linked List
*
ListNodes

ListNodes in Linked List
public class ListNode { // fill the comments
private String data; //
private ListNode link; //
/** */
public ListNode () {
link = null; //
data = null; //
}
/** */
public ListNode (String newData, ListNode linkValue) {
data = newData;
link = linkValue;
}

*

ListNodes in Linked List (cont’d)
/** */
public void setData (String newData) {
data = newData;
}
/** */
public String getData () {
return data;
}
*

ListNodes in Linked List (cont’d)
/** */
public void setLink (ListNode newLink) {
link = newLink;
}
/** */
public ListNode getLink () {
return link;
}
}
*

Linked List Class
A linked list class uses the ListNode class
The variable head refers to the first node in the list.
*

Linked List of String
public class StringLinkedList { //write comments
private ListNode head;
/** */
public StringLinkedList () {
head = null; //
}
*

Linked List of String (cont’d)
/** */ public void showList () {
ListNode position = head; //
while (position != null) {
System.out.println (position.getData ());
position = position.getLink (); //
}
}
*

Linked List of String (cont’d)
/** */
public int length () {
int count = 0;
ListNode position = head; //
while (position != null) { //
count++; //
position = position.getLink (); //
}
return count;
}
*

Linked List of String (cont’d)
/** */
public void addANodeToStart (String addData) {
head = new ListNode (addData, head);
}
/** */
public void deleteHeadNode () {
if (head != null)
head = head.getLink (); //
else {
System.out.println (“Deleting from an empty list.”);
System.exit (0);
}
}
*

Linked List of String (cont’d)
/* Returns a reference to the first node containing the target data. If target is not on the list, returns null. */
private ListNode find (String target) {
boolean found = false; //
ListNode position = head;
while ((position != null) && !found) { //
String dataAtPosition = position.getData ();
if (dataAtPosition.equals (target))
found = true;
else
position = position.getLink (); //
}
return position;
}
}
*

Linked List of String (cont’d)
/** */
public boolean onList (String target) {
return find (target) != null;
}
*

Lab Exercises
Write a demo program that tests the discussed methods
add the courses you took into the linked list.
Show all courses in the linked list
Delete the first course you added
check some courses whether they are in the list or not.
*

java.util.ArrayList

+
ArrayList
()

+add(o: Object) : void

+add(index: int, o: Object) : void

+clear(): void

+contains(o: Object): boolean

+get(index: int) : Object

+indexOf(o: Object) : int

+isEmpty(): boolean

+lastIndexOf(o: Object) : int

+remove(o:
Object): boolean

+size(): int

+remove(index: int) : Object

+set(index: int, o: Object) : Object

Appends a new element o at the end of this list.

Adds a new element o at the specified index in this list.

Removes all the elements from this list.

Returns t
rue if this list contains the element o.

Returns the element from this list at the specified index.

Returns the index of the first matching element in this list.

Returns true if this list contains no elements.

Returns the index of the last matching elemen
t in this list.

Removes the element o from this list.

Returns the number of elements in this list.

Removes the element at the specified index.

Sets the element at the specified index.

Creates an empty list.