Csc 201-lecture 14

CSC 201 Lecture-14

Agenda • Stacks • Queues • Linked Lists

Data Structure • A data structure may be designed to store data for the purpose of working on it. • Data Structures for Programming languages : – Arrays – Linked Lists – Stacks – Queues …

Linked Lists • Linked list is a data structure which can be defined as follows: a linked list is either empty (null) or a reference to a node having a reference to a linked list. • A linked list consists of a chain of objects o same type, linked together by pointers/references from one object to another.

Concepts (Linked List) Node

Concepts (Linked List) contd.. • Node is an abstract entity that might hold any kind of data + reference for building linked lists. • Representation of a node: class Node { A node data String data; Next: Reference Node next; To Next node/null }

Building Linked List • Create an object of type Node by invoking a noargument constructor. Node firstNode = new Node(); This creates a Node object whose instance variables are both initialized to value ‘null’. • Lets put some data into our first node. firstNode.data = “item1”;

• Similarily to create 2 nodes, we could say Node secondNode = new Node(); Node thirdNode = new Node(); • To insert data into second and third nodes, we say secondNode.data = “item2”; thirdNode.data = “item3”;

• How about the ‘next’ instance variable of class Node? – We set the next fields to build the linked list.

firstNode.next = secondNode; secondNode.next = thirdNode; thirdNode.next = null;

Operations on Linked Lists • Insert: To insert a node into a linked list, easiest place is at the beginning of list. NewNode New node to be added! Ex: NewItem

item1

item3 item2 l null

FirstNode

SecondNode

ThirdNode

Node NewNode = firstNode; Create a new node for the beginning firstNode = new Node(); firstNode.data = “item0”; firstNode.next = NewNode;

LinkedList.java

class node { node next; String data; } // My class node is created public class Main {

public static void main(String[] args) { // creating 3 nodes node first = new node(); node sec = new node(); node third = new node(); //Inserting data into first node System.out.println("First element inserted"); first.data = "item1"; first.next = sec;

sec.data = "item2"; sec.next = third; third.data = "item3"; third.next = null; System.out.println("Inserting a new node"); node newnode = first; first = new node(); first.data = "item0"; first.next = newnode; String str = ""; System.out.println(“Printing the linked list nodes data"); for(node x = first; x != null; x=x.next ) str = str + x.data + " "; System.out.println(str); } }

Linked list Vs Arrays 1) It does not require contiguous memory. 2) It can grow indefinitely (you do not need to know how much memory to allocate as we did with arrays). 3) If memory is of importance then the linked list implementation is your best choice.

Stacks • Stack is based on a LIFO (Last In First Out) policy. • Examples of stack? • Two fundamental operations : push and pop. • Push : Adds the item to the top of the list. • Pop : Removes an item from the top of the list.

Queues • A Queue data structure is based on the policy of a FIFO ( First In First Out ). • Examples of Queues ? • Operations : add() and remove(). Check other possible operations offer(), peek(), poll().