Topic 14Li k d Li tLinked Lists"All the kids who did great in high school writing gg gpong games in BASIC for their Apple II would get to college, take CompSci 101, a data structures course and when they hit the pointers business theircourse, and when they hit the pointers business their brains would just totally explode, and the next thing you knew, they were majoring in Political Science because law school seemed like a better idea."-Joel SpolskypyThanks to Don Slater of CMU for use of his slides.CS 307 Fundamentals of Computer Science Linked Lists1Attendance Question 1What is output by the following code?ArrayList<Integer> a1 = new ArrayList<Integer>();ArrayList<Integer> a2 = newArrayList<Integer>();ArrayList<Integer> a2 = new ArrayList<Integer>();a1.add(12);a2.add(12);System.out.println( a1 == a2 );A. No output due to syntax errorB. No output due to runtime errorC. falseD. trueCS 307 Fundamentals of Computer Science Linked Lists2Dynamic Data StructuresDynamicdata structuresDynamicdata structures– They grow and shrink one element at a time, normally without some of the inefficiencies ofnormally without some of the inefficiencies of arrays–as opposed to a static container like an arraypp yBig O of Array Manipulations–Access the kth element– Add or delete an element in the middle of the array while maintaining relative order–adding element at the end of array? space avail? no space avail? add element at beginning of an arrayCS 307 Fundamentals of Computer Science Linked Lists3–add element at beginning of an arrayObject ReferencesRecall that an object reference is a variable that stores the address of an objectA reference can also be called a pointerThey are often depicted graphically:studentJohn Smith407253.57Linked Lists4References as LinksObject references can be used to create links between objectsSuppose a Student class contained a ftthdbj treference to another Student objectJohn Smith407253.57Jane Jones588213.72Linked Lists5References as LinksReferences can be used to create a variety of linked structures, such as a linked list:studentListLinked Lists6Linked ListsAlill ti f lff til bj t lldA linear collection of self-referential objects, called nodes, connected by other links–linear: for every node in the list, there is one and only one node y, ythat precedes it (except for possibly the first node, which may have no predecessor,) and there is one and only one node that succeeds it, (except for possibly the last node, which may have no successor)no successor)– self-referential: a node that has the ability to refer to another node of the same type or even to refer to itselfnode of the same type, or even to refer to itself– node: contains data of any type, including a reference to another node of the same data type, or to nodes of different data typesnode of the same data type, or to nodes of different data types– Usually a list will have a beginning and an end; the first element in the list is accessed by a reference to that class, and the last CS 307 Fundamentals of Computer Science Linked Lists7y,node in the list will have a reference that is set to nullAdvantages of linked listsLi k d li d i h h i kLinked lists are dynamic, they can grow or shrink as necessaryLinked lists can be maintained in sorted order simply by inserting each new element at the propersimply by inserting each new element at the proper point in the list. Existing list elements do not need to be movedto be movedLinked lists arenon-contiguous;the logicalLinked lists are non-contiguous; the logical sequence of items in the structure is decoupled from any physical ordering in memoryCS 307 Fundamentals of Computer Science Linked Lists8yp y g yNodes and ListsA different way of implementing a listEach element of a Linked List is a separate Node object.Each Node tracks a single piece of data plus ac ode t ac s a s g e p ece o data p usa reference (pointer) to the next Create a new Node very time we addCreate a new Node very time we add something to the ListRemove nodes when item removed from listRemove nodes when item removed from list and allow garbage collector to reclaim that memoryCS 307 Fundamentals of Computer Science Linked Lists9memoryA Node Classpublic class Node<E> {public class Node<E> {private E myData;private Node myNext;public Node()public Node(){ myData = null; myNext = null; }public Node(E data, Node<E> next){myData = data; myNext = next; }{y;y;}public E getData(){ return myData; }public Node<E> getNext(){ return myNext; }public void setData(Et data){Dt dt}{myData = data;}public void setNext(Node<E> next){ myNext = next; }}CS 307 Fundamentals of Computer Science Linked Lists10}One Implementation of a Linked ListTh N d h th i lidThe Nodes show on the previous slide are singly linkeddf ltth tdith–a node refers only to the next node in the structure–it is also possible to havedoubly linkednodesit is also possible to have doubly linkednodes. – The node has a reference to the next node in the structure and the previous node in the structure pas wellHow is the end of the list indicated– myNext = null for last node– a separate dummy node class / objectCS 307 Fundamentals of Computer Science Linked Lists11Interfaces and Standard JavaFinally, an alternate implementation to an ADTSpecify a List interface–Java has thisCkiImplement in multiple ways–ArrayListCookieArrayList– LinkedListWhich is better?Which is better?CS 307 Fundamentals of Computer Science Linked Lists12A Linked List Implementationpublic class LinkedList<E> implements Ilist<E>public class LinkedList<E> implements Ilist<E>private Node<E> head;private Node<E> tail;private int size;public LinkedList(){head = null;tail = null;tail = null;size = 0;}}LinkedList<String> list = new LinkedList<String>();LinkedListmyHead iMySizenullll0CS 307 Fundamentals of Computer Science Linked Lists13myTailnullWriting MethodsWhen trying to code methods for Linked Lists draw pictures!– If you don't draw pictures of what you are trying to do it is very easy to make mistakes!CS 307 Fundamentals of Computer Science Linked Lists14add methodadd to the end of listspecial case if emptysteps on following slidespublic void add(Object obj)public void add(Object obj)CS 307 Fundamentals of Computer Science Linked Lists15Add Element - List Empty (Before)head tail sizellll0nullnull0ObjectitemCS 307 Fundamentals
View Full Document