Programming - 6 - Data Structures

Question 1

What is a Linked List?

Answer 1

• linear collection of self-referential objects connected by reference links
• self referential classes contain reference instance variables linking to objects, forming dynamic data structures

Question 2

Linked List code example

Answer 2

public class ListNode {

private Object data; //data

private ListNode next; // self-reference

public ListNode (Object newData, ListNode newNext) {

data = newData;

next = newNext;

}

public Object getData() {…}

public ListNode getNext() {…}

public void setData(..) {…}

public void setNext(..) {…}

}

public class List {

protected ListNode firstNode;

protected ListNode lastNode;

protected String name;

public void insertAtBack (Front(Object newData) {}

public Object removefromBack/Front() {}

public ListNode getFirst() {}

public String toString() {}

public List (String listName)

Question 3

What is a Stack?

Answer 3

• dynamic data strcuture in which data can be inserted from the top (LIFO)
• implemented using a linked list (through composition or inheriting)

Question 4

Stack code through composition and inheriting

Answer 4

public class Stack extends List {

public Stack() { super(“Stack”);}

public void push (Object data) {…}

public Object pip() {…}

}

public class Stack{ // composition

private List stackList;

public Stack() {stackList = new List(“Stack”); }

.

.

.

}

Question 5

What is a Queue?

Answer 5

• Data inserted at back, removed at front (FIFO)
• used in discrete event simulations to store “events” in spooling systems
• Implemented through composition, main methods: enqueue, dequeue