Data Structures using Java Part 7: Linked Lists Part 2 (Doubly Linked)

private field
————–
private field is invisible and inacessable to other classes.
Reasons:
1. To prevent data to be corrupted by other classes.
2. You can improve the implementation without causing the other classes to fail.

public class Date{

	private int day;
	private int month;

	public void setMonth(int m){
		month  = m;
	}

	public Date(int month , int date){
	// implementation and error checking code
	}
}
public class Evil{

	public void tamper(){

	Date d = new Date(10,10,2010); // this step is possible

	// these are not going to work!
	d.day =2000;
	d.setMonth(56);
	}
}

Interfaces
————
The interface of a class is made up of two things:
1. prototype for public methods and
2. the descriptions of the method behaviour.

Abstract Data Types(ADT)
——————————
ADT is a class(s) that has a well defined interface, but whose implementation details are firmly hidden from other classes.

Invarient
———-
Invarient is a fact about a data structure that is always true. (assuming there are no bugs). For example the “Date” object always represents a valid date.
Not all classes are ADTs. Some are just store data(no invarients).

The SList ADT
—————–

Another advantage of having a seperate SList class is that it enforces two invarients:
1. “size” is always correct.
2. list is never circularly linked.

Both of these goals are accomplised through simple Java mechanisms. Only the SList methods can change the lists.

SList ensures this:
1. The fields of the SList class are private. The “head” and “size” are private.
2. No method of SList returns an SListNode.

Doubly Linked Lists
———————

Doubly linked list

Inserting or deleting an element at the front of list is easy:

public void deleteFront(){
	if (head != null){
	head = head.next;
	size--;
	}
}

Inserting or deleting the item from the end of the list takes a lot of time in traversals.

public class DListNode{

	int item;
	DListNode next; // reference to the next node in list
	DListNode prev;// referencet to the previous node in the list

}

public class DList{

	private DListNode head; // points to start of the list
	private DListNode tail; // points to the end of the list
}

Insert and delete items at both ends in constant running time.
Removes the tail node (at least 2 items in DList):

tail.prev.next = null;
tail = tail.prev;

Sentinel
———
A special node that does not represent an item. It is to be noted that the sentinel node does not store an item.

Circularly linked Doubly linked list
————————————

 // no changes here
 public class DListNode{

	int item;
	DListNode next; // reference to the next node in list
	DListNode prev;// referencet to the previous node in the list

}

// changes here
public class DList{

	private DListNode head; // head will point to the sentinel
	private int size; // keeps track of the size of the list excluding the sentine.
}

DList invarients with sentinel:
——————————–
1. For any DList data structure d, d.head will never be null.
2. For any DListNode x, x.next is never null.
3. For any DListNode x, x.perv is never null.
4. For any DListNode x, if x.next is == y, then y.perv ==x.
5. For any DListNode x, x.prev ==y, then y.next ==x.
6. A DLists “size” field is number of DListNodes, NOT COUNTING sentinel. The sentinel is always hidden.
7. In empty DLists, the sentinels next and prev point to itselfs.

Advertisements
Data Structures using Java Part 7: Linked Lists Part 2 (Doubly Linked)