1、链表的增删查
// to run this program: C>java LinkList2App
class Link
{
public int iData;
public Link next;
public Link(int id)
{
iData = id;
}
public void displayLink()
{
System.out.print("{" + iData + "} ");
}
} //==========================================
class LinkList
{
private Link first;
public LinkList()
{
first = null;
}
public boolean isEmpty()
{
return (frist == null );
}
public void insertFirst(int id)
{
Link newLink = new Link(id);
newLink.next = first;
first = newLink;
}
public Link deleteFirst()
{
if(!isEmpty())//链表不为空
{
Link temp = first;
first = first.next;
return temp;
}
else //链表为空
return null;
}
public Link find(int key)
{
Link current = first;
while(current != null && current.iData != key)
{
current = current.next;
}
if(current == null)//没有找到
return null;
else //已经找到
return current;
}
public Link delete(int key)
{
Link current = first;
Link previous = first;
while(current != null && current.iData != key)
{
previous = current;
current = current.next;
}
if(current == null)//没有找到
return null;
if(current == first)//已经找到且是第一个元素
first = first.next;
else //已经找到且不是第一个元素
previous.next = current.next;
return current;
}
public void displayList()
{
System.out.print("List (first-->last): ");
Link current = first;
while(current != null)
{
current.displayLink();
current = current.next;
}
System.out.println("");
}
}
//=============================================================
class LinkListApp
{
public static void main(String[] args)
{
LinkList theList = new LinkList();
theList.insertFirst(22);
theList.insertFirst(44);
theList.insertFirst(66);
theList.insertFirst(88);
theList.displayList();
theList.deleteFirst();
Link f = theList.find(44);
if( f != null)
System.out.println("Found link with key " + f.iData);
else
System.out.println("Can't find link");
Link d = theList.delete(66);
if( d != null )
System.out.println("Deleted link with key " + d.iData);
else
System.out.println("Can't delete link");
theList.displayList();
}
}
2、双端队列
链表有两个指针first和last，一个指向头节点，一个指向尾节点。
// to run this program: C>java FirstLastApp
class Link
{
public long dData;
public Link next;
public Link(long d)
{ dData = d; }
public void displayLink()
{ System.out.print(dData + " "); }
}
//============================================
class FirstLastList
{
private Link first;
private Link last;
public FirstLastList()
{
first = null;
last = null;
}
public boolean isEmpty()
{ return first==null; }
public void insertFirst(long dd)
{
Link newLink = new Link(dd);
if( !isEmpty() ) //链表不为空
{
newLink.next = first;
first = newLink;
}
else //链表为空
{
first = newLink;
last = newLink;
}
}
public void insertLast(long dd)
{
Link newLink = new Link(dd);
if( !isEmpty() ) //链表不为空
{
last.next = newLink;
last = newLink;
}
else //链表为空
{
first = newLink;
last = newLink;
}
}
public Link deleteFirst()
{
if(!isEmpty()) //链表不为空
{
Link temp = first;
if(first.next == null) //链表只有一个元素
{
first = null;
last = null;
}
else //链表元素的个数大于1
first = first.next;
return temp;
}
else
return null;
}
public void displayList()
{
System.out.print("List (first-->last): ");
Link current = first;
while(current != null)
{
current.displayLink();
current = current.next;
}
}
}
//==================================================
class FirstLastApp
{
public static void main(String[] args)
{
FirstLastList theList = new FirstLastList();
theList.insertFirst(22);
theList.insertFirst(44);
theList.insertFirst(66);
theList.insertLast(11);
theList.insertLast(33);
theList.insertLast(55);
theList.displayList();
theList.deleteFirst();
theList.deleteFirst();
theList.displayList();
}
}
3、有序链表
// to run this program: C>java SortedListApp
class Link
{
public long dData;
public Link next;
public Link(long dd)
{
dData = dd;
next = null;
}
public void displayLink()
{ System.out.print(dData + " "); }
}
//===================================================
class SortedList
{
private Link first;
public SortedList()
{ first = null; }
public boolean isEmpty()
{ return (first==null); }
public void insert(long key)
{
Link newLink = new Link(key);
Link previous = first;
Link current = first;
while(current != null && key > current.dData)
{
previous = current;
current = current.next;
}
if(previous == null && current == null) //链表为空的情况插入
first = newLink;
else if(current !=null && current == first)//链表非空，在链表头插入的情况
{
newLink.next = current;
first = newLink;
}
else //链表非空，在非链表头插入的情况
{
previous.next = newLink;
newLink.next = current;
}
}
public Link remove()
{
if(!isEmpty())
{
Link temp = first;
first = first.next;
return temp;
}
else
return null;
}
public void displayList()
{
System.out.print("List (first-->last): ");
Link current = first;
while(current != null)
{
current.displayLink();
current = current.next;
}
}
}
//==============================================================
class SortedListApp
{
public static void main(String[] args)
{
SortedList theSortedList = new SortedList();
theSortedList.insert(20);
theSortedList.insert(40);
theSortedList.displayList();
theSortedList.insert(10);
theSortedList.insert(30);
theSortedList.insert(50);
theSortedList.displayList();
theSortedList.remove();
theSortedList.displayList();
}
}
4、使用有序链表对数组排序
// to run this program: C>java ListInsertionSortApp
class Link
{
public long dData;
public Link next;
public Link(long dd)
{ dData = dd; }
}
//==============================================
class SortedList
{
private Link first;
public SortedList()
{ first = null; }
public SortedList(Link[] linkArr)
{
first = null;
for(int j=0; j<linkArr.length; j++)
insert( linkArr[j] );
}
public void insert(Link k)
{
Link previous = null;
Link current = first;
while(current != null && k.dData > current.dData)
{
previous = current;
current = current.next;
}
if(previous == null && current == null) //链表为空的情况插入
first = k;
else if(current !=null && current == first)//链表非空，在链表头插入的情况
{
k.next = current;
first = k;
}
else //链表非空，在非链表头插入的情况
{
previous.next = k;
k.next = current;
}
}
public Link remove()
{
Link temp = first;
first = first.next;
return temp;
}
} // end class SortedList
//==============================================
class ListInsertionSortApp
{
public static void main(String[] args)
{
int size = 10;
Link[] linkArray = new Link[size];
for(int j=0; j<size; j++)
{
int n = (int)(java.lang.Math.random()*99);
Link newLink = new Link(n);
linkArray[j] = newLink;
}
System.out.print("Unsorted array: ");
for(int j=0; j<size; j++)
System.out.print( linkArray[j].dData + " " );
System.out.println("");
SortedList theSortedList = new SortedList(linkArray);
for(int j=0; j<size; j++)
linkArray[j] = theSortedList.remove();
System.out.print("Sorted Array: ");
for(int j=0; j<size; j++)
System.out.print(linkArray[j].dData + " ");
System.out.println("");
}
}
5、双向双端链表
// to run this program: C>java DoublyLinkedApp class Link { public long dData; public Link next; public Link previous; public Link(long d) { dData = d; } public void displayLink() { System.out.print(dData + " "); } } //================================================== class DoublyLinkedList { private Link first; private Link last; public DoublyLinkedList() { first = null; last = null; } public boolean isEmpty() { return first==null; } public void insertFirst(long dd) { Link newLink = new Link(dd); if(!isEmpty()) //链表不为空 { first.previous = newLink; newLink.next = first; first = newLink; } else //链表为空 { last = newLink; first = newLink; } } public void insertLast(long dd) { Link newLink = new Link(dd); if(!isEmpty()) //链表不为空 { last.next = newLink; newLink.previous = last; last = newLink; } else //链表为空 { last = newLink; first = newLink; } } public Link deleteFirst() { if(!isEmpty()) //链表不为空 { Link temp = first; if(first.next == null)//链表只有一个元素 { first = null; last = null; } else { //链表的元素个数大于1 first.next.previous = null; first = first.next; } return temp; } else //链表为空 return null; } public Link deleteLast() { if(!isEmpty()) //链表不为空 { Link temp = last; if(first.next == null) //链表只有一个元素 { first = null; last = null; } else //链表的元素个数大于1 { last.previous.next = null; last = last.previous; } return temp; } else //链表为空 return null; } public boolean insertAfter(long key, long dd) { Link current = first; while(current != null && current.dData != key) { current = current.next; } if(current == null) //链表为空 return false;
Link newLink = new Link(dd);
if(current==last) //链表不为空，在链表尾插入 { newLink.next = null; newLink.previous = current; current.next = newLink; last = newLink; return true; } else //链表不为空，在非链表尾插入 { newLink.next = current.next; current.next.previous = newLink; newLink.previous = current; current.next = newLink; return true; } } public Link deleteKey(long key) { Link current = first; while(current != null && current.dData != key) { current = current.next; } if(current == null) //链表为空 return null; if(current == first && current == last)//链表只有一个元素的情况 { first = null; last = null; } else if(current == first && current != last)//链表元素大于一个，删第一个元素 { first = first.next; first.previous = null; } else if(current != first && current == last)//链表元素大于一个，删最后一个元素 { last = last.previous; last.next = null; } else //链表元素大于一个，删非第一个和非最后一个元素 { current.previous.next = current.next; current.next.previous = current.previous; } return current; } public void displayForward() { System.out.print("List (first-->last): "); Link current = first; while(current != null) { current.displayLink(); current = current.next; } System.out.println(""); } public void displayBackward() { System.out.print("List (last-->first): "); Link current = last; while(current != null) { current.displayLink(); current = current.previous; } System.out.println(""); } } //===================================================== class DoublyLinkedApp { 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); theList.displayForward(); theList.displayBackward(); theList.deleteFirst(); theList.deleteLast(); theList.deleteKey(11); theList.displayForward(); theList.displayBackward(); theList.insertAfter(22, 77); theList.insertAfter(33, 88); theList.displayForward(); } }
6、迭代器
// to run this program: C>java InterIterApp import java.io.*; class Link { public long dData; public Link next; public Link(long dd) { dData = dd; } public void displayLink() { System.out.print(dData + " "); } } //========================================================== class LinkList { private Link first; public LinkList() { first = null; } public Link getFirst() { return first; } public void setFirst(Link f) { first = f; } public boolean isEmpty() { return first==null; } public ListIterator getIterator() { return new ListIterator(this); } public void displayList() { Link current = first; while(current != null) { current.displayLink(); current = current.next; } System.out.println(""); } } //============================================================= class ListIterator { private Link current; private Link previous; private LinkList ourList; public ListIterator(LinkList list) { ourList = list; reset(); } public void reset() { current = ourList.getFirst(); previous = null; } public boolean atEnd() { return (current.next==null); } public void nextLink() { previous = current; current = current.next; } public Link getCurrent() { return current; } public void insertAfter(long dd) { Link newLink = new Link(dd); if( ourList.isEmpty() ) { ourList.setFirst(newLink); current = newLink; } else { newLink.next = current.next; current.next = newLink; nextLink(); } } public void insertBefore(long dd) { Link newLink = new Link(dd); if(previous == null) { newLink.next = ourList.getFirst(); ourList.setFirst(newLink); reset(); } else { newLink.next = previous.next; previous.next = newLink; current = newLink; } } public long deleteCurrent() { long value = current.dData; if(previous == null) { ourList.setFirst(current.next); reset(); } else { previous.next = current.next; if( atEnd() ) reset(); else current = current.next; } return value; } } //========================================================== class InterIterApp { public static void main(String[] args) throws IOException { LinkList theList = new LinkList(); ListIterator iter1 = theList.getIterator(); long value; iter1.insertAfter(20); iter1.insertAfter(40); iter1.insertAfter(80); iter1.insertBefore(60); while(true) { System.out.print("Enter first letter of show, reset, "); System.out.print("next, get, before, after, delete: "); System.out.flush(); int choice = getChar(); switch(choice) { case 's': if( !theList.isEmpty() ) theList.displayList(); else System.out.println("List is empty"); break; case 'r': iter1.reset(); break; case 'n': if( !theList.isEmpty() && !iter1.atEnd() ) iter1.nextLink(); else System.out.println("Can't go to next link"); break; case 'g': if( !theList.isEmpty() ) { value = iter1.getCurrent().dData; System.out.println("Returned " + value); } else System.out.println("List is empty"); break; case 'b': System.out.print("Enter value to insert: "); System.out.flush(); value = getInt(); iter1.insertBefore(value); break; case 'a': System.out.print("Enter value to insert: "); System.out.flush(); value = getInt(); iter1.insertAfter(value); break; case 'd': if( !theList.isEmpty() ) { value = iter1.deleteCurrent(); System.out.println("Deleted " + value); } else System.out.println("Can't delete"); break; default: System.out.println("Invalid entry"); } } } public static String getString() throws IOException { InputStreamReader isr = new InputStreamReader(System.in); BufferedReader br = new BufferedReader(isr); String s = br.readLine(); return s; } public static char getChar() throws IOException { String s = getString(); return s.charAt(0); } public static int getInt() throws IOException { String s = getString(); return Integer.parseInt(s); } }