New User Special Price Expires in

Let's log you in.

Sign in with Facebook


Don't have a StudySoup account? Create one here!


Create a StudySoup account

Be part of our community, it's free to join!

Sign up with Facebook


Create your account
By creating an account you agree to StudySoup's terms and conditions and privacy policy

Already have a StudySoup account? Login here

Computer Science II Chapter 5 Linked Lists

by: Gaoqi Zheng

Computer Science II Chapter 5 Linked Lists CSE 214

Marketplace > Stony Brook University > ComputerScienence > CSE 214 > Computer Science II Chapter 5 Linked Lists
Gaoqi Zheng
Stony Brook U
View Full Document for 0 Karma

View Full Document


Unlock These Notes for FREE

Enter your email below and we will instantly email you these Notes for Computer Science II

(Limited time offer)

Unlock Notes

Already have a StudySoup account? Login here

Unlock FREE Class Notes

Enter your email below to receive Computer Science II notes

Everyone needs better class notes. Enter your email and we will send you notes for this class for free.

Unlock FREE notes

About this Document

Java Datastructure Chapter 5 Linked Lists
Computer Science II
Ahmad Esmaili
Class Notes




Popular in Computer Science II

Popular in ComputerScienence

This 55 page Class Notes was uploaded by Gaoqi Zheng on Thursday February 25, 2016. The Class Notes belongs to CSE 214 at Stony Brook University taught by Ahmad Esmaili in Spring 2016. Since its upload, it has received 28 views. For similar materials see Computer Science II in ComputerScienence at Stony Brook University.

Similar to CSE 214 at Stony Brook U

Popular in ComputerScienence


Reviews for Computer Science II Chapter 5 Linked Lists


Report this Material


What is Karma?


Karma is the currency of StudySoup.

You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 02/25/16
Linked Lists Chapters 5 Fundamentals • A singly-linked list is a sequence of data elements (of the same type) arranged one after another conceptually. • Each element is stored in a node. • Each node also contains a link that connects this node to the next node in the list. Fundamentals (cont’d) • A special link called the head references the first node in a list. • Some lists may also have a special link called the tail that references the last node in a list. • A cursor is a link that points to one of the nodes of the list. • A list may be empty. (i.e. head = tail = null). Conceptual Picture data link 12 31 20 null Node head Actual Picture WORD ADDRESS CONTENTS 1000 31 (2ndnumber) 1002 1008 st 1004 12 (1 number) 1006 1000 1008 20 (3 number) 1010 0 head 1012 1004 Defining a Node public class IntNode { private int data; private IntNode link; // IntNode methods } Constructor public IntNode(int initialData) { data = initialData; link = null; } Accessor Methods public int getData() { return data; } public IntNode getLink() { return link; } Mutator Methods public void setData(int newData) { data = newData; } public void setLink(IntNode newLink) { link = newLink; } Defining a Linked List public class IntList { private IntNode head; private IntNode tail; private IntNode cursor; // IntList methods } Constructor public IntList() { head = null; tail = null; cursor = null; } Add to head of list newNode.setLink(head);element); head = newNode; 12 31 20 X 10 X head newNode Add a new head of list public void addNewHead(int element) { IntNode newNode = new IntNode(element); newNode.setLink(head); head = newNode; if (tail == null) tail = head; cursor = head; } Add after cursor (general) newNode.setLink(cursor.getLink()); cursor.setLink(newNode); 12 X 31 20 15 X cursor newNode Add after cursor (general) newNode.setLink(cursor.getLink()); cursor.setLink(newNode); cursor = newNode; 12 X 31 20 X 15 X cursor newNode Add integer after cursor public void addIntAfter(int element) { IntNode newNode = new IntNode(element); if (cursor == null) { head = newNode; tail = newNode; cursor = newNode; } Add integer after cursor (cont’d) else { newNode.setLink (cursor.getLink()); cursor.setLink(newNode); cursor = newNode;//advance cursor if (cursor.getLink() == null) tail = cursor; } } Watch out! cursor.setLink(newNode); newNode.setLink(cursor.getLink()); 12 X 31 20 15 X cursor newNode Remove after cursor (general) cursor.setLink(cursor.getLink().getLink()); 12 31 20 X cursor Why do we have to remove AFTER the cursor node ? we just remove Remove after cursor public void removeIntAfter() { if (cursor != tail) { cursor.setLink( cursor.getLink() .getLink()); if (cursor.getLink() == null) tail = cursor;//last node } } Remove head of list public void removeHead() { if (head != null) head = head.getLink(); if (head == null) tail = null; cursor = head; } Working with cursor public boolean advanceCursor() { if (cursor != tail) { cursor = cursor.getLink(); return true; } else return false; } Working with cursor (cont’d) public void resetCursor() { cursor = head; } public boolean isEmpty() { return (cursor == null); } “Traverse” a list nodePtr = head; nodePtr = nodePtr.getLink(); 12 31 20 X X X head nodePtr Length of List public int listLength() { IntNode nodePtr = head; int answer = 0; while (nodePtr != null) { answer++; nodePtr = nodePtr.getLink(); } return answer; } Point of Caution • Why didn’t we define nodePtr this way in listLength? IntNode nodePtr = new IntNode(0); nodePtr = head; • Use “new” only when you actually need a new node! • If you are defining a variable to reference a node that already exists, don’t use “new”! Search the list public boolean listSearch(int target) { IntNode nodePtr = head; while (nodePtr != null) { if (target == nodePtr.getData()) { cursor = nodePtr; return true; } nodePtr = nodePtr.getLink(); } return false; } Set cursor to specific position public boolean listPosition(int position) { IntNode nodePtr = head; int i = 1; if (position <= 0) throw ...etc... while (i<position && nodePtr != null){ nodePtr = nodePtr.getLink(); i++; } if (nodePtr != null) cursor = nodePtr; return (nodePtr != null); Copy a list public static IntList listCopy (IntList source) { IntList newList = new IntList(); IntNode nodePtr = source.head; while (nodePtr != null) { newList.addIntAfter (nodePtr.getData()); nodePtr = nodePtr.getLink(); } return newList; } Additional IntList Methods public int getNodeData() throws EmptyListException { if (cursor == null) throw new EmptyListException(...); return (cursor.getData()); } public void setNodeData(int element) throws EmptyListException { if (cursor == null) throw new EmptyListException(...); cursor.setData(element); } The Bag ADT using Lists public class IntLinkedBag implements Cloneable { private IntList data; private int manyItems; Implementation (cont’d) public IntLinkedBag() { manyItems = 0; data = new IntList(); } No need to worry about the bag’s capacity since a linked list has no maximum capacity! Only one constructor is needed. Implementation (cont’d) public int getCapacity() { return Integer.MAX_VALUE; } public int size() { return manyItems; } Implementation (cont’d) public void ensureCapacity (int minimumCapacity) { // no work is needed } Implementation (cont’d) public void add(int element) { data.addNewHead(element); manyItems++; } Order of Complexity? Implementation (cont’d) public int countOccurrences(int target) { int answer = 0; int index; data.resetCursor(); for (index=0; index<manyItems; index++) { if (target == data.getNodeData()) answer++; data.advanceCursor(); } return answer; } Order of Complexity? Removing an element • Other methods can be implemented in a similar manner. • Watch out! remove isn’t easy with singly linked lists! • How can we remove an element with the structure we have? • Use listSearch to move cursor to location of target • BUT we can’t remove that node! Trailing pointers • Use a trailing pointer to keep track of the previous node to the current node we’re examining. • Once we find the node we want to remove, the trailing pointer will point to the previous node which we can connect to the next node after the current node. Example (remove 9) 12 31 X 9 20 X X X head prevPtr X nodePtr Step 1: Step 2 : Step 2 prevPtr = nunodePtr = nodePtr.getLink() Step 3: prevPtr.setLink(nodePtr.getLink()) Implementation public boolean remove(int target) { IntNode nodePtr = head; IntNode prevPtr = null; while (nodePtr != null && nodePtr.getData() != target) { prevPtr = nodePtr; nodePtr = nodePtr.getLink(); } if (nodePtr != null) prevPtr.setLink(nodePtr.getLink()); return (nodePtr != null); Linked List V ariations • Doubly-linked list prev data next 12 31 20 head tail Linked List V ariations • Circular-linked list 12 31 20 head Linked List V ariations • Linked list with dummy head node 12 31 20 null dummy node - always the first node of a list head - thus, head is never null the list Arrays vs. Linked Lists Arrays • Better for random access to any data value • Better if number of elements is known and doesn’t vary much Linked Lists • Better for additions and removals (other data elements do not need to be moved) • Better if number of elements varies greatly and is not known at runtime The Object Data Type • A variable of type Object is capable of holding a reference to any kind of object. • Let ObjectB be a subclass of ObjectA. ObjectA a; ObjectB b; • a = b; OK, widening conversion is automatic • b = a; NO, narrowing conversion is not automatic b = (ObjectB) a; Wrapper Classes • Primitive data types (not objects): byte short int long float double char boolean • Wrapper classes are object classes: Byte Short Integer Long Float Double Character Boolean • To perform arithmetic on data in a wrapper class, you need to extract the data first example: Integer intObject = new Integer(214); int i = intObject.intValue(); Generic Node public class Node { private Object data; private Node link; // Node methods } Constructor public Node(Object initialData) { data = initialData; link = null; } Using the constructor: Integer intObject = new Integer(214); Node newNode = new Node(intObject); getData() public Object getData() { return data; } Using the accessor: Integer I = (Integer)newNode.getData(); System.out.println(I.intValue()); setData() public void setData(Object newData) { data = newData; } Using the mutator: Integer J = new Integer(220); newNode.setData(J); A generic linked list public class List { private Node head; private Node tail; private Node cursor; // List methods } A sample method public void addNewHead(Object element) { Node newNode = new Node(element); newNode.setLink(head); head = newNode; if (tail == null) tail = head; cursor = head; } Another method public boolean listSearch(Object target) { Node nodePtr = head; while (nodePtr != null) { if (target.equals(nodePtr.getData())) { cursor = nodePtr; return true; } nodePtr = nodePtr.getLink(); } return false; CAREFUL! target could be null } (code not shown here) Using a generic data structure • To store data in the list, put it in a wrapper (if necessary) before you insert it into the list. • If you extract data from the list, remove it from the wrapper (if necessary) before processing it. • REMEMBER: If you extract data from the list, the accessor will return an Object which has to be typecast (narrowed). Iterators (optional) public class List implements Iterator If a class implements the Iterator interface, it must provide the following methods: public boolean hasNext() public Object next() public void remove() • Using a loop, iterators allow you to step through a collection, like a list, just as an index allows you to step through an array.


Buy Material

Are you sure you want to buy this material for

0 Karma

Buy Material

BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.


You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

Why people love StudySoup

Jim McGreen Ohio University

"Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

Kyle Maynard Purdue

"When you're taking detailed notes and trying to help everyone else out in the class, it really helps you learn and understand the I made $280 on my first study guide!"

Steve Martinelli UC Los Angeles

"There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."


"Their 'Elite Notetakers' are making over $1,200/month in sales by creating high quality content that helps their classmates in a time of need."

Become an Elite Notetaker and start selling your notes online!

Refund Policy


All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email


StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here:

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.