Linked Lists Plus

Linked Lists Plus last updated 3/22/07

Complexity Trade-offs Summary of chapter 6 performance tables. Operation Class Constructor

Unsorted Sorted Unsorted Sorted Array Array Linked List Linked List linear linear (initialization constant constant (init.) of elements)

Search logarithmi (isThere/retriev linear linear linear c e) reset/getNextIte constant constant constant constant m lengthIs/isFull constant constant constant constant linear (assume Insert/remove keeping linear constant constant first chron. order) Insert/remove linear (assume search time search time linear middle chron. order) +constant +constant Insert/remove search+consta search+consta constant constant end nt nt search+consta search+consta search+consta Delete linear nt nt nt Resizing linear linear constant constant Memory 25-100% 25-100% size/(size+4) size/(size+4) utilization

Head Nodes Managing the insertion and deletion of the first node is a special case in sorted lists. The middle and last elements are noted to be similar in management. The special case of handling the first node can be eliminated by creating a special "head node" •

pre-allocated like a regular node

•

store no data in it

•

head points to it, and the head node points to the real first element of the list

//constructor code LLObjectNode head = new LLObjectNode(); //initialize head node in const head.setInfo(null);

public void insert (Comparable item) // Adds a copy of item to list. { LLObjectNode newNode = new LLObjectNode(); reference to node being inserted LLObjectNode prevLoc; trailing reference LLObjectNode location; traveling reference

// // //

location = head.getLink(); prevLoc = head; // this variable is removed: 'moreToSearch' // Find insertion point. while (location != null) //loop until item is < element { if (item.compareTo(location.getInfo()) > 0) list element is larger than item { prevLoc = location; location = location.getLink(); } } // Prepare node for insertion. newNode.info(item); // Insert node into list. newNode.setLink(location);

//

prevLoc.setLink(newNode); numItems++; } Trade a little space for improvement in program time and simpler programming.

Circular linked list My preference for circular linked lists is to build upon the notion of a head node (See above). This is a deviation from Dale/Joyce/Weems. Idea: Rather than having a NULL at the last element, point back to first element.

//Set up initial tight looped list LLObjectNode head; // in constructor head = new LLObjectNode(); head.setInfo(null); head.setLink(head); //No changes //except the LLObjectNode LLObjectNode

to insertion code as w/ head node search stopping criteria prev = head; cur = head.getLink(); //get first node

while(cur != head && cur.getInfo().compareTo(newValue)<0){ prev = cur; cur = cur.getLink(); } ....

The above is the algorithm for searching as well.

Doubly Linked Lists

The problem with singly linked lists is that direction of access is limited to one direction. Traversing the list in reverse order is not an option. Access to the end of the list is linear in time. The insertion and removal routines had to maintain an auxiliary variable to perform the updates. A doubly linked lists maintains two references per node: "next" and "previous". Of course, now, twice as many links have to be maintained. Reverse order processing is easier.

I also prefer to implement doubly linked lists with the circular concept as well.

public abstract class DoublyLinkedList implements ListInterface prev info next { protected class ListNode // Used to hold references to list nodes for the linked list implementation { protected Comparable info; // the info in a list node protected LLObjectNode next; // a link to the next node on the list protected LLObjectNode prev; // a link to the previous node on the list } protected LLObjectNode head; the first node on the list protected int numItems; elements in the list protected LLObjectNode currentPos; position for iteration public LinkedList() // Creates an empty list object. { numItems = 0; head = new ListNode();

// reference to // Number of // Current

head.next = head; head.prev = head; currentPos = head; }

Insertion into a doubly linked list public void insert (Listable item) // Adds a copy of item to list. { ListNode newNode = new ListNode(); being inserted ListNode prevLoc; reference ListNode location; traveling reference boolean moreToSearch;

// reference to node // trailing //

location = head.next; prevLoc = head; moreToSearch = (location != null); // Find insertion point. while (moreToSearch) { if (item.compareTo(location.info) < 0) is larger than item moreToSearch = false; else { prevLoc = location; location = location.next; moreToSearch = (location != null); } } // Prepare node for insertion. newNode.info = (Listable)item.copy(); // Insert node into list. newNode.prev = location.prev; newNode.next = location; location.prev.next = newNode; location.prev = newNode;

//1 //2 //3 //4

// list element

numItems++; }

Array Implementation of Lists A linked list could be implemented in an array.

The elements might be stored in an array in any order, and “linked” by their indexes. We keep a separate list of available nodes. Tracking free space:

List Applications Heap storage management All free segments of memory are kept in a list. When an object allocation occurs, the free list is searched for a block of contiguous storage that is sufficient for the object. The excess space is recorded again in the free list. When the garbage collector determines that an object is no longer accessible, the space used by the object is placed back into the free list. There may be times that adjacent blocks of memory are free. Coalescing allows these adjacent free space blocks to be formed into a larger block. If not done, the memory will be fragmented to a point that large objects cannot be allocated the necessary space.

Organization of files on disk The directory space and file information is kept in list type of organization.