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

Advanced Programming

by: Mireya Heidenreich

Advanced Programming CS 2213

Mireya Heidenreich
GPA 3.55

Jeffery Ronne

Almost Ready


These notes were just uploaded, and will be ready to view shortly.

Purchase these notes here, or revisit this page.

Either way, we'll remind you when they're ready :)

Preview These Notes for FREE

Get a free preview of these Notes, just enter your email below.

Unlock Preview
Unlock Preview

Preview these materials now for free

Why put in your email? Get access to more of this material and other relevant free materials for your school

View Preview

About this Document

Jeffery Ronne
Class Notes
25 ?




Popular in Course

Popular in ComputerScienence

This 4 page Class Notes was uploaded by Mireya Heidenreich on Thursday October 29, 2015. The Class Notes belongs to CS 2213 at University of Texas at San Antonio taught by Jeffery Ronne in Fall. Since its upload, it has received 7 views. For similar materials see /class/231371/cs-2213-university-of-texas-at-san-antonio in ComputerScienence at University of Texas at San Antonio.

Similar to CS 2213 at UTSA

Popular in ComputerScienence


Reviews for Advanced Programming


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: 10/29/15
CS 2213 Spring 2009 Linked Lists Linked list store lists of data elements linked together with pointers Linked Lists are important because of their simplicity They re usually slower to access than arrays because of cache issues but are easier to shrink and grow as data is added or removed from them They are one of the easiest data structures to code up especially in a garbage collected programming language They re re cursive structure makes them a natural fit for being built and operated on by recursive functions and they are a primitive construct in many functional pro gramming languages such as Lisp and ML They are really easy to implement in Java but there is a generic version called javautilLinkedList In C the standard template library implementation is called std list What is a Linked List In its simplest form a linked list is a connection of nodes each of which contains some data and a pointer to the next node in a chain Since all of the other nodes can be reached by following pointers from the first one a pointer to the first node can be taken to represent the entire list The last node of course does not need a pointer to a quotnext node so some special value usually NULL in its place The code for such a linked list structure is quite simple If the data being stored is single character the following declaration is sufficient struct node char data struct node next Each node is a dynamically allocated instance of this data structure The Recursive Structure Note that there is a reference to the node structure within the definition of the node structure This is is what makes the data structure recursive It is not a problem because it is not a whole node structure but rather just a pointer to a node structure that is contained in each node structure If you look back at our example linked list the next field of the first node which contains 39A39 points to the second node which contains 39B39 And as we said that we can represent the whole list 39A39 39B39 39c39 by a pointer to the first node this pointer to the second node can be considered to represent the list 39B39 39c39 And the next field of the 39B39 node which points to the 39c39 node can be considered to represent the list C For consistency we can also consider the NULL value for the next field of the 39c39 node to represent an empty list In this way every list can be considered to be either NULL or Node containing the data for the first element and a pointer to a sublist containing the rest of the list ML and Lisp lists are constructed and deconstructed in exactly this manner and the operations provided are 0 construct a new list by adding a new element to the front of an old list struct node conschar first struct node rest I struct node linkedlist linkedlist mallocsizeofstruct node linkedlistgtdata first linkedlistgtnext rest 0 access the first data element of a list char firststruct node linkedlist return linkedlistgtdata 0 access the rest of the list struct node reststruct node linkedlist return oldlistgtnext lterating over the elements of the list can be done pretty easily with something like struct node nodeptr linkedlist while nodeptr nodeptrgtnext NULL sum nodeptrgtdata You can also gets the same effect with a recursive function int sumstruct node linkedlist I return linkedlistgtdata sumlinkedlistgtnext This is a minimal linked list You can add a next field to any structure and ini tialize it to point to another instance of the same structure and so on eventually terminating in a NULL pointer and you have a linked list The basic operations are so simple that they re often embedded directly in the code or provided as language primitives in Lisp and ML Comparison to Dynamic Arrays Dynamic arrays support random access eg what is the nth element in con stant time whereas linked lists require iteration over 71 nodes to get to the nth In addition on modern computers dynamic arrays are much more cache friendly so iteration will be much faster over dynamic arrays On the other hand linked lists are more exible one can generally insert or delete an element in the middle or end of a linked list assuming one has a pointer itera tor to it in constant time In addition linked lists are generally easier to implement especially in language that have garbage collection but not realloc eg Java Variations and Construction of Wrapped Linked List For a minimal linked list you can add a next field to any structure making the structure a node and initialize the next pointer to point to another instance of the same structure and so on eventually terminating in a NULL pointer and coupled with a first head pointer you have a linked list Some common variations on the linked list are 1 to include a pointer to the last aka tail node of the linked list in addition to a pointer to the first aka head 2 to include in each node a pointer to the previous node in addition to the next node and or 3 the use of sentinel nodes before the first and last list A linked list with both previous and next nodes is known as a quotdoubly linked list In some cases it is sufficient to use a pointer to the first node to represent the entire list but this can be awkward if one list is to be accessed modified in more than one location especially if you are going to be adding nodes to the front of the list or back of the list at various points in the program In the former case the pointer to the head of the list changes and changes with each insertion and it is necessary to maintain consistency among all of the users of the list In the latter case in order to avoid traversing the whole list it is desirable to maintain a last pointer pointing to the last node of the list This tail pointer needs to be available at any program point might remove from or add to the end of the list For simple cases just having a first variable and a last variable may be sufficient but if you need to access the list from lots of different functions copying around both variables can get old An alternative is to wrap the linked list in some kind of structure and of the list This allows one to use a single unchanging pointer to represent a particular linked list as it evolves A pointer to that outer linked list structure can then be used to represent the list and operations can modify the outer structure and the internal nodes it points to without invalidating that pointer to the outer structure An additional step towards modularity can be made by putting the operations into a separate functions For a simple linked list that is only constructed in a single location at a single time and then accessed sequentially this may be overkill compared to just embedding the pointer operations directly but for the more complex variants of linked lists or for more complex usage patterns it can help make the program more modular The C structures for such a linked list containing an integer in each node might be declared as struct node I int data struct node prev struct node next struct linkedlist struct node first struct node last Operations The following outlines the steps to inserting and removing nodes from a doubly linked list inserting a node 1 malloc space for a struct node 2 initialize the data to be stored in the node 3 link the node s next and prev links to its neighbors NULL if it is at the beginning or end 4 link the preceding neighbor s next link to the node use the list s first link instead if the node is being inserted at the beginning of the list 5 link the succeeding neighbor s prev link to the node use the list s last link instead if the node is being inserted at the end of the list removing a node 1 connect the preceding neighbor s next link to the succeeding neighbor use the list s first link instead if the node is being removed from the beginning of the list 2 connect the succeeding neighbor s prev link to the preceding neighbor use the list s last link instead if the node is being removed from the end of the list 3 deallocate the node In a singly linked list without last links it is of course unnecessary to update the previous last links It is still however necessary to update the preceding neigh bor s next link Unfortunately in a singly linked list there is no way given just a pointer to a node to get access to the preceding neighbor So although a singly linked list is itself simpler the code for looping over its nodes and acting upon them is often more complex since it may needs to be able to access both the quotprecedingquot and quotcurrentquot node In general linked lists operations often need special cases if the node being ma nipulated is the first or last in the list or if the list is or is becoming empty So when writing linked list operations pay special attention eg think through and imagine or draw diagrams to what should happen in each of those cases Some times special cases in the code can be eliminated by either using a pointer to the previous node s next pointer in place of a pointer to a node or by adding extra dummy sentinel nodes at the beginning and end of the linked list An Example Removal of Matching Nodes from Singly and DoublyLinked Lists For example if one wants to remove all node whose data equals x for a doubly linked list pointed to by the variable 11 the code might look like struct node p llgtfirst iterate over the nodes while p NULL if the node matches x delete the node if pgtdata x struct node n p p p gtnext connect predecessor to its new successor if ngtprev NULL ngtprevgtnext ngtnext else


Buy Material

Are you sure you want to buy this material for

25 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

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."

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!"

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."


"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.