Linked list is a data structure consisting of a group of nodes which together represent a sequence. Under the simplest form, each node is composed of a datum and a reference (in other words, a link) to the next node in the sequence; more complex variants add additional links. This structure allows for efficient insertion or removal of elements from any position in the sequence.

A linked list whose nodes contain two fields: an integer value and a link to the next node. The last node is linked to a terminator used to signify the end of the list.

Simple Linked List:

////////////////////////////////////////////////////////////////

class Link

{

public int iData; // data item

public double dData; // data item

public Link next; // next link in list

// -------------------------------------------------------------

public Link(int id, double dd) // constructor

{

iData = id; // initialize data

dData = dd; // ('next' is automatically

} // set to null)

// -------------------------------------------------------------

public void displayLink() // display ourself

{

System.out.print("{" + iData + ", " + dData + "} ");

}

} // end class Link

////////////////////////////////////////////////////////////////

class LinkList

{

private Link first; // ref to first link on list

// -------------------------------------------------------------

public LinkList() // constructor

{

first = null; // no links on list yet

}

// -------------------------------------------------------------

public boolean isEmpty() // true if list is empty

{

return (first==null);

}

// -------------------------------------------------------------

// insert at start of list

public void insertFirst(int id, double dd)

{ // make new link

Link newLink = new Link(id, dd);

newLink.next = first; // newLink --> old first

first = newLink; // first --> newLink

}

// -------------------------------------------------------------

public Link deleteFirst() // delete first item

{ // (assumes list not empty)

Link temp = first; // save reference to link

first = first.next; // delete it: first-->old next

return temp; // return deleted link

}

// -------------------------------------------------------------

public void displayList()

{

System.out.print("List (first-->last): ");

Link current = first; // start at beginning of list

while(current != null) // until end of list,

{

current.displayLink(); // print data

current = current.next; // move to next link

}

System.out.println("");

}

// -------------------------------------------------------------

} // end class LinkList

////////////////////////////////////////////////////////////////

class LinkListApp

{

public static void main(String[] args)

{

LinkList theList = new LinkList(); // make new list

theList.insertFirst(22, 2.99); // insert four items

theList.insertFirst(44, 4.99);

theList.insertFirst(66, 6.99);

theList.insertFirst(88, 8.99);

theList.displayList(); // display list

while( !theList.isEmpty() ) // until it's empty,

{

Link aLink = theList.deleteFirst(); // delete link

System.out.print("Deleted "); // display it

aLink.displayLink();

System.out.println("");

}

theList.displayList(); // display list

} // end main()

} // end class LinkListApp

Laboratory Exercise:

Using the Linked List showed above, write a program that will compute the total cost purchased by a customer. The program has a menu that will show the items and the prices. The program will ask the user the item to purchase and after the user chooses the item, the program will ask the quantity purchased. The user can add more item purchased as soon as the user quit from the menu. Note: the Item No, Qty and Price should be saved in the list.

List of Products

Item No. Items Price (Dhs)

101 T-Shirt 70.25

102 Polo 160.75

103 Long Sleeve 250.45

104 Pants 300.35

105 Shoes 200.85

Menu

[1] Enter Order

[2] Print Receipt

[3] Exit

Enter your choice: 1

Enter Item No.:101

Enter Quantity:2

----------------------------------------

Menu

[1] Enter Order

[2] Print Receipt

[3] Exit

Enter your choice: 1

Enter Item No.:102

Enter Quantity:1

-----------------------------------------

Menu

[1] Enter Order

[2] Print Receipt

[3] Exit

Enter your choice: 2

Item No. Price Qty Cost

101 70.25 2 140.50

102 160.75 1 160.75

Total Cost: 301.25

12