COP 3540 Data Structures with OOPDifferent Storage StructureLinksLinks.Basic TypesReferencesA Simple Linked ListThe LinkList ClassThe insertFirst MethodSlide 10insertFirst() Be sure to understand what is going on hereSlide 12Slide 13Slide 14Slide 15Slide 16Finding and Deleting Specified LinksSlide 18Slide 19Slide 20Pictures for the Soul… ‘Memory Addresses’Double-Ended Lists (not doubly-linked list)Pictures:Slide 24Linked-List EfficiencyQuestions?1/27COP 3540 Data Structures with OOP Chapter 5Linked Lists2/27 Different Storage StructureArrays:Some real advantages and disadvantages depending on whether or not the array was sorted AND what you wanted to do•Insert•Delete•Search…Second most commonly used data storage structure after arrays: the Linked List.Extremely versatile.Will discuss strengths and weaknesses3/27Links“In a linked list, each data item is embedded in a link.  (I sometimes call these nodes or cells).(You may not use the link in the API for link operations in your program assignments.)Each link object contains data – (any kind; any amount) and a reference (points to the next item in the list).4/27Links.Consider:class Link{public int iData //some datapublic double dData //more datapublic Link next; // reference to next link } // end class definitionThis kind of class definition is called self-referential, because it contains a link that points to the next node that is of the same type as itself.We can have many data items in a link. But the key is the next reference to the ‘next’ link.5/27 Basic TypesNote: ‘next’ is only a reference to the next link. Next has the address of the next object or null.For ‘next’ to have meaning, there must be an object created and its address placed into ‘next.’6/27ReferencesIn an array, we merely add one (1) to access the next physical item.In a linked-list, we follow a chain of links – from one link to another to find a desired link. It is unlikely you have the direct access of a specific link to directly access (although processing linked lists does allow you to save off addresses, if you wish…)7/27 A Simple Linked ListWe will insert items and delete items at the beginning of the list anddisplay items in a linked list.Here’s the Link Classclass Link{public int iData;public double dData; Let’s make these ‘public’ for now…public Link next;// ------------------------------------------------------------------------ public Link (int id, double dd) // Constructor {iData = id;dData = dd; } // end Constructor // ----------------------------------------------------------------------- public void displayLink() {System.out.print(“{ + iData + “,” + dData + “} ”); } // end displayLink() } // end class LinkClearly the Constructor builds the data in the link (but not the next field) and the display() prints it out.Why does the Constructor not build the ‘next’ field??8/27The LinkList ClassSpecial class. Note: your authors call this class, LinkList.Only contains the address of the first element in the linked list.Class LinkList{ private Link first; // reference to an object (special object) of type Link. Name is ‘first.’// ------------------------------------------- public void LinkList() // Constructor {first = null; // Can see the value of ‘first’ is null – until we start building links. // It doesn’t point to anything yet. } // end constructor public boolean isEmpty() { return (first==null); } // end isEmpty()// other methods.} // end LinkList9/27The insertFirst MethodWe are now going to build and insert nodes into an existing linked list.See next slide:First points to next link (value of 42) which points to next link (value of 7), etc. Last link points to null.Now insert first() a new Link w/value of 33 at first part of the Linked List which then points to the previous first link, who has value of 42…Consider the drawing and then insertfirst():10/2742 7 98nullLinked List – already builtFirst1442 7 98nullrearFirst1433rearIdentify the parts: links, next, values, first, …Linked ListDataNext (link)Insert a node into the linked list.11/27insertFirst() Be sure to understand what is going on hereAccomplish this with an insertFirst() method:public void insertFirst (int id, double dd){ Link newLink = new Link (id,dd); // creates a new object with initial data values. newLink.next = first; // newLink  old first// new link now points to what used to be the first linkfirst = newLink;// Now, first points to the new link we just inserted. first  newLink} // end insertFirst()  means: ‘links to’ or ‘points to’ or ‘references’---------------------------------------------------------------------------------------------------------Let’s look at all the necessary classes and objects…class Link, class LinkedList and class LinkedListApp.(Think of this design like State, StateDriver or StateArr, and the Main app.)12/27class Link (Note: this is only the link (node) itself. The object….) { public int iData; // data item public double dData; // data item public Link next; // next link in list note: self-referential// ------------------------------------------------------------- public Link(int id, double dd) // constructor (Note only the data is built here). // Handling next was handled by the client. { iData = id; // initialize data Notice this only dData = dd; // ('next' is automatically set to null) } public void displayLink() // display yourself { System.out.print("{" + iData + ", " + dData + "} "); } } // end class Link(Like an entity class….. It is the data item – has data and pointer to next data…)The Link class13/27class 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); }public void insertFirst(int id, double dd) // make new link // insert at start of list {Link newLink = new Link(id, dd); // creates new Link with data. newLink.next = first; // newLink --> old first