DOC PREVIEW
TRINITY CSCI 1321 - Linked Lists

This preview shows page 1-2-3 out of 10 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 10 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 10 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 10 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 10 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Slide 1Slide 2Slide 3Slide 4Slide 5Slide 6Slide 7Slide 8Slide 9Slide 101Linked Lists2/26/20092Opening Discussion■Let's look at some solutions to the interclass problem.■Do you have any questions about the assignment or the readings?■Do you have any questions about the midterm?■Let's finish our array based queue quickly.■What is a list? What are the things that you can do with a list?3The List ADT■The next step up the ADT ladder is the list. Basically a list provides general access so you can add, remove, or search for things at random locations in the list.■Java has an interface called List in java.util. Let's go look at that.4An Array Based List■So how could we implement the list interface using an array?■What methods of that implementation would be “fast”? Which ones would be “slow”?■What do the terms fast and slow mean here in O terms and what operations are being considered for that?5Linked Lists■There is an alternate method of implementing the list interface called the linked list. It is strong where an array list is weak, but weak where an array list is strong.■A linked list is made of nodes and each node knows about one or two of its neighbors (has pointers to them).■We move around linked lists by “walking” from node to node.■Adding and removing can be very fast and always require very few memory writes.6Types of Linked Lists■Linked lists can be implemented in many ways. The basic characteristic is that we only keep a reference to one node and nodes then link to one another.■The linking can be single or double. A doubly linked list has nodes that know about both the next and the previous elements.■Linked lists can also be circular. In a circular linked list, the first element links around to the back one.■For optimization purposes, lists can keep track of a head and a tail, but that isn't required.7Implementing a Singly Linked List■Let's work together to build an implementation of a singly linked list.■We will implement the java.util.List interface, but we won't have time to implement all of the methods.8Sentinels■A sentinel is an extra node in the list the represents the “end” of the list and doesn't store data.■The purpose of the sentinel is to remove special cases. The next of the sentinel is what we have called head.■They are most useful in a doubly linked list where the previous of the sentinel is tail.9Implementing a Doubly Linked List■Now let's implement java.util.List with a doubly linked list with a sentinel. The list will also be circular.■You should notice that this implementation never has to check for null because no references in the list should ever be null. This simplifies the code significantly. We also implicitly get a head and a tail with no extra work. If you don't have a sentinel you will write a lot of extra checks for nulls and even more to include a tail.10Minute Essay■When do you want to have a review session for the midterm?■Remember that the design for assignment #3 is due today.■Next Tuesday is the midterm and the due date for assignment #3.■Interclass problem – Write a simple linked list that you can use for the memory function of our graphical RPC. Have a main that puts some numbers on your list then pulls them


View Full Document

TRINITY CSCI 1321 - Linked Lists

Documents in this Course
Recursion

Recursion

11 pages

Iterators

Iterators

10 pages

Actors

Actors

9 pages

Recursion

Recursion

15 pages

Recursion

Recursion

10 pages

Threads

Threads

7 pages

Trees

Trees

11 pages

Load more
Download 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 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 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?