Java 单链表操作

代码参考 

《Java语言程序设计（进阶篇）》- chapter 25 线性表、栈、队列和优先队列

片段一：定义节点结构

public class Node { //定义节点结构 int value; Node next; Node(int element){ value=element; } public Node() { // TODO Auto-generated constructor stub } } 片段二：定义链表操作

import java.util.Scanner; public class MyLinkList { int size=0; Node head,tail; public MyLinkList() { // TODO Auto-generated constructor stub this.head=null; this.tail=null; } public void addFirst( int value) { Node newNode=new Node(value); if(size==0) { //newNode.next=head; head=newNode; tail=newNode; size++; } } public void addLast(int value){ Node newNode=new Node(value); if(tail==null) { addFirst(value); } else { tail.next=newNode; tail=newNode; size++; } } public void add(int index,int value){ Node newNode=new Node(value); Node node1=head; if(size<=index){ addLast(value); } else if(index==0) addFirst(value); else{ for(int i=0;i<index-1;i++) node1=node1.next; Node temp=node1.next; node1.next=newNode; newNode.next=temp; size++; } } public void removeLast(){ if(head==null){ System.out.println("sorry,the list is empty"); return; } else if(size==1){ size--; head=tail=null; //留意head的处理 } else { Node temp=head; for(int i=0;i<size-2;i++) temp=temp.next; tail=temp; tail.next=null; size--; } } public void removeFirst(){ if(head==null){ System.out.println("sorry,the list is empty"); return; } else{ head=head.next; size--; if(size==0) tail=null; //留意此处的tail的处理 } } public void remove(int index){ if(size<index+1){ System.out.println("sorry there is no matching capcity"); return; } else if(index==0) removeFirst(); else if(index==size-1) removeLast(); else{ Node current=head; for(int i=0;i<index-1;i++){ current=current.next; } current.next=(current.next).next; size--; } } public void print(Node head1){ while(head1!=null) { System.out.print(head1.value+" "); head1=head1.next; } System.out.println( ); } }片段三：测试函数

package offerExam; public class TestLinkList { public static void main(String[] args){ MyLinkList linklist=new MyLinkList(); linklist.removeLast(); linklist.print(linklist.head); linklist.addFirst(3); linklist.print(linklist.head); linklist.removeFirst(); linklist.print(linklist.head); linklist.addLast(4); linklist.print(linklist.head); linklist.removeLast(); linklist.print(linklist.head); linklist.add(2, 5); linklist.print(linklist.head); linklist.add(4, 7); linklist.print(linklist.head); linklist.add(3, 6); linklist.print(linklist.head); linklist.add(2, 10); linklist.print(linklist.head); linklist.removeLast(); linklist.print(linklist.head); } } 运行结果：

sorry,the list is empty 3 4 5 5 7 5 7 6 5 7 10 6 5 7 10