单链表的实现

节点的封装：

package SingleLinkedList;
/*
 * 但链表表节点的封装
 * 一个Node节点包含的数据是元素和下一个节点的连接
 */
public class Node <E>{
	public E e;
	public Node next;
	public Node(E e, Node next) {
		this.e = e;
		this.next = next;
	}
	public Node(E e) {
		this(e, null);
	}
	public Node() {
		this(null, null);
	}
	@Override
	public String toString() {
	  return e.toString();
	}

}

节点的封装：

package SingleLinkedList;
/*
 * 单链表的实现
 */
public class SingleLinkedList<E> {
  private Node nullhead;  //声明空头节点
  private int size; // 链表存放的元素
  public SingleLinkedList() {
	  nullhead =new Node(null,null);
	  size=0;
  }
//  在链表头位置添加元素
  public void addFirst(E e){
     add(0,e);	
  }
  public void addLast(E e) {
	 add(size,e);
  }
  //在任意位置添加元素
  public void add(int index, E e) {
	// TODO Auto-generated method stub
	if(index<0||index>size) {
		throw new IllegalArgumentException("add failed,index is invaild");
		
	}
	Node prev =nullhead;
	for(int i=0;i<index;i++) {
		prev =prev.next;
	}
//  创建一个待插入的节点node
	Node node =new Node(e);
//  将该节点挂接到链表中(要注意顺序，先连尾部先)
//	node.next=prev.next;
//	prev.next=node;
	prev.next =new Node(e,prev.next); //等同于上面两行代码，比较简洁
//   维护size
	size++; 
}
 // 删除元素首个
  public Object removeFirst() {
	  return remove(0);
  }
  public E removerLast() {
	  return remove(size-1);
  }
  public E remove(int index) {
	// TODO Auto-generated method stub
	if(index<0||index>=size) {
		throw new IllegalArgumentException("remove failed,index is invaild");
	}
	Node prev =nullhead; //
//  通过这个for循环，找到待删除的节点的前一个节点
	for(int i=0;i<index;i++) {
		prev=prev.next;
	}
    Node delnode =prev.next;//待删除的节点
    prev.next =delnode.next; //开始连接
    delnode.next=null; //断开连接
    size--;
	return (E) delnode.e;
}
  
   public void set(int index,E e) {
	   if(index<0||index>=size) {
		   throw new IllegalArgumentException("set failed ,index is invaild");
	   }
//   先拿到头节点，以便遍历
	   Node cur =nullhead.next;
	   int i=0;
	   while(cur!=null) {
		      if(i==index) {
		    	  cur.e=e;
		      }
		      i++;
		     cur= cur.next;
	   }
   }
   public E get(int index) {
	  if(index<0||index>=size) {
		  throw new IllegalArgumentException("get failed ,index is invaild");
	  }
	  Node cur =nullhead.next;
	  int i=0;
	  while(cur!=null) {
		    if(i==index) {
		    	return (E) cur.e;
		    }
		    i++;
		    cur=cur.next;
	  }
	   
	return null;
   }
   public E getfirst() {
	   return  get(0);
   }
   public boolean isEmpty() {
	   return size==0;
   }
   public int getSize() {
	   return size;
   }
//重写打印输出
public String toString() {
    StringBuilder res=new StringBuilder();
    res.append("linkedList:");
    Node cur =nullhead.next;//第一个节点，也就是头节点
    while(cur!=null) {
    	res.append(cur+"->");
    	cur=cur.next;
    }
    res.append("null");
	return res.toString();
}
}

测试：

package SingleLinkedList;

public class SingleLinkedListTest {
public static void main(String[] args) {
	SingleLinkedList lis =new SingleLinkedList<Integer>();
	lis.addFirst(10); //往头部添加元素
	for(int i=1;i<6;i++) {
		lis.add(i, i); //往插入元素
	}
	lis.addLast(10);
	System.out.println(lis); //ok添加没有问题测试没有问题
	lis.remove(1);
	lis.removeFirst();
	lis.removerLast();
	System.out.println(lis); //ok删除测试没有问题;
	lis.set(1, 100);
	System.out.println(lis); //ok改没有问题
	System.out.println( "查第三个下标元素是"+lis.get(3)); //查
	System.out.println("获取元素个数:"+lis.getSize()); //查
}
}

结果：