DOC PREVIEW
UT CS 307 - Topic 14 Linked Lists

This preview shows page 1-2-17-18-19-35-36 out of 36 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 36 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 36 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 36 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 36 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 36 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 36 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 36 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 36 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

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 188What 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 Structures8Dynamicdata structures8Dynamicdata 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 y8Big 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 References88Recall that an object reference is a variable that stores the address of an object8A reference can also be called a pointer8They are often depicted graphically:studentJohn Smith407253.57Linked Lists4References as Links88Object references can be used to create links between objects8Suppose a Student class contained a ftthdbj treference to another Student objectJohn Smith407253.57Jane Jones588213.72Linked Lists5References as Links88References can be used to create a variety of linked structures, such as a linked list:studentListLinked Lists6Linked Lists8Alill ti f lff til bj t lld8A 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 lists8Li k d li d i h h i k8Linked lists are dynamic, they can grow or shrink as necessary8Linked 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 moved8Linked 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 Lists88A different way of implementing a list8Each element of a Linked List is a separate Node object.8Each 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 8Create a new Node very time we addCreate a new Node very time we add something to the List8Remove nodes when item removed from list8Remove 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 List8Th N d h th i lid8The 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 well8How 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 Java88Finally, an alternate implementation to an ADT8Specify a List interface–Java has thisCki8Implement in multiple ways–ArrayListCookieArrayList– LinkedList8Which is better?8Which 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 Methods88When 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 method88add to the end of list8special case if empty8steps on following slides8public 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 of Computer Science Linked Lists16Add Element - List Empty (After)head tail size11


View Full Document

UT CS 307 - Topic 14 Linked Lists

Documents in this Course
Midterm 2

Midterm 2

15 pages

Midterm 1

Midterm 1

15 pages

Syllabus

Syllabus

24 pages

s

s

8 pages

Midterm 1

Midterm 1

14 pages

Midterm 2

Midterm 2

14 pages

Recursion

Recursion

14 pages

Midterm 1

Midterm 1

16 pages

Load more
Download Topic 14 Linked Lists
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Topic 14 Linked Lists and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Topic 14 Linked Lists 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?