♥According to the book by: Mark Allen Weiss Doubly Linked Lists sometimes to traverse lists backwards. The standard implementation does not help here, but the solution is simple. Merely add an extra field to the data structure, containing a pointer to the previous cell. The cost of this is an extra link, which adds to the space requirement and also doubles the cost of insertions and deletions, because you no longer have to refer to a key by using a pointer to the previous cell.[Book of Data Structure and Algorithm Analysis]
♥According to Wikipedia, a more sophisticated kind of linked list is a doubly-linked list or two-way linked list. Each node has two links: one points to the previous node, or points to a null value or empty list if it is the first node; and one points to the next, or points to a null value or empty list if it is the final node.[WIKIPEDIA]
B.Illustration
A doubly-linked list containing three integer values: the value, the link forward to the next node, and the link backward to the previous node
C. java Code
//constructor class
class Link {
public int iData;
public Link next;
public Link previous;
public Link(int id) {
iData = id;
}
public String toString() {
return "{" + iData + "} ";
}
}
//a class that has the methods or operation of doubly linked list
class DoublyLinkedList {
private Link first;
private Link last;
public DoublyLinkedList() {
first = null;
last = null;
}
public boolean isEmpty() {
return first == null;
}
public void insertFirst(int dd) {
Link newLink = new Link(dd);
if (isEmpty()){
last = newLink;
}else{
first.previous = newLink;
}
newLink.next = first;
first = newLink;
}
public void insertLast(int dd) {
Link newLink = new Link(dd);
if (isEmpty()){
first = newLink;
}else {
last.next = newLink;
newLink.previous = last;
}
last = newLink;
}
public Link deleteFirst() {
Link temp = first;
if (first.next == null){
last = null;
}else{
first.next.previous = null;
}
first = first.next;
return temp;
}
public Link deleteLast() {
Link temp = last;
if (first.next == null){
first = null;
}else{
last.previous.next = null;
}
last = last.previous;
return temp;
}
public boolean insertAfter(int key, int dd) {
Link current = first;
while (current.iData != key) {
current = current.next;
if (current == null){
return false;
}
}
Link newLink = new Link(dd);
if (current == last) {
newLink.next = null;
last = newLink;
} else {
newLink.next = current.next;
current.next.previous = newLink;
}
newLink.previous = current;
current.next = newLink;
return true;
}
public Link deleteKey(int key) {
Link current = first;
while (current.iData != key) {
current = current.next;
if (current == null)
return null;
}
if (current == first){
first = current.next;
}else{
current.previous.next = current.next;
}
if (current == last){
last = current.previous;
}else{
current.next.previous = current.previous;
}
return current;
}
public String toString() {
String str = "List (first-->last): ";
Link current = first;
while (current != null) {
str += current.toString();
current = current.next;
}
System.out.println("");
System.out.print("List (last-->first): ");
current = last;
while (current != null) {
str += current.toString();
current = current.previous;
}
return str;
}
}
//main class that executes the operation on the doubly linked lists
public class MainClass {
public static void main(String[] args) {
DoublyLinkedList theList = new DoublyLinkedList();
theList.insertFirst(22);
theList.insertFirst(44);
theList.insertFirst(66);
theList.insertLast(11);
theList.insertLast(33);
theList.insertLast(55);
System.out.println(theList);
theList.deleteFirst();
theList.deleteLast();
theList.deleteKey(11);
System.out.println(theList);
theList.insertAfter(22, 77);
theList.insertAfter(33, 88);
System.out.println(theList);
}
}
D.References
[Book of Data Structure and Algorithm Analysis]Mark Allen Weiss
[WIKI]http://en.wikipedia.org/wiki/Linked_list
[WIKI]http://en.wikipedia.org/wiki/File:Doubly-linked-list.svg
No comments:
Post a Comment