Java实现链表

1、Node.java(链表结点类实现）

package test2;

public class Node {
    // 为了避免外部对象直接访问Node的成员
    // 建议尽量降低访问权限
    private int value;  // 节点的值
    private Node next;  // 节点的 next对象

    // 为Node类型提供必要的构造器和get、set方法
    public Node(int value){
        this.value = value;
        next = null;
    }

    public void setValue(int value) {
        this.value = value;
    }

    public void setNext(Node next) {
       this.next = next;
    }

    public int getValue() {
        return this.value;
    }

    public Node getNext() {
        return this.next;
    }
}

2、List.java（链表类的实现）

package test2;
import test2.Node;
public class List {
    // 单链表或者循环链表
    private Node head; // 链表首节点，其index为0
    private Node last; // 链表尾结点
    public List() {
        head = last = null;
    }

    // 将指定节点添加到此列表的结尾
    public boolean insert(Node node) {
        return insert(length(), node);
    }

    // 根据value生成Node对象，添加至指定位置
    public boolean insert(int index, int value) {
        return insert(index, new Node(value));
    }

    // 将Node对象添加至指定位置
    // 如果 index<0 或者 index>length() ，则返回false
    public boolean insert(int index, Node node) {
        // **补充代码
	if(index<0||index>length())
	return false;
	int count =0;

	Node pointer = head;
	if(index==0&&this.isEmpty()){
	head=node;
	last=node;
	return true;
	}
	if(index==0){
	pointer=head;
	head=node;
	node.setNext(pointer);
	return true;
	}
	
	Node quote = head;
	while(count!=index-1){
	++count;
	pointer=pointer.getNext();
	}
	if(index!=length()){
	quote = pointer.getNext();
	pointer.setNext(node);
	node.setNext(quote) ;
	}else{
	pointer.setNext(node);
	last=node;
	}
	return true;
    }

    // 将指定元素插入此列表的开头
    public boolean insertToHead(Node node) {
        return insert(0, node);
    }

    // 返回此列表中指定位置处的元素
    private Node get(int index) {
	int count =0;
    if(index<0||index>this.length()){
    System.out.println("输入元素非法！");
    return null;
    }
	Node pointer = head;
	while(count!=index){
	pointer=pointer.getNext();
	++count;
	}
	return pointer;
    }

    // 将此列表中指定位置的元素value值更新为指定值
    public void setData(int index, int value) {
        // **补充代码
        Node quote = this.get(index);
        quote.setValue(value);
    }

    // 返回此列表的元素个数
    // 因为length()只在类体内部调用，可以设置为private权限
    private int length() {
	int count=0;
	Node quote = this.head;
	if(head==null)
	return 0;
	while(quote!=last){
	quote = quote.getNext();
	++count;
	}
	return ++count;
    }

    // 如果此 循环链表不包含元素，则返回 true
    public boolean isEmpty() {
 	return  this.head==null;
    }

    // 返回此列表的第一个元素
    public Node getHead() {
        return head;
    }

    // 返回此列表的最后一个元素
    public Node getLast() {
        return last;
    }

    // 遍历输出每个节点的序号和value
    public void printList() {
	Node quote = head;
     for(int i=0;i=length()){
            return null;
        }else{
        Node previousQuote = this.get(index-1);
        previousQuote.setNext(quote.getNext());
		}
        return quote; 
    }

    // 将参数list中的所有元素按照原有顺序添加至此列表的结尾
    boolean addAll(List list) {
     Node quote = list.head;
     for(int i =0;i<=list.length();i++){
       this.insert(this.length(),new Node(quote.getValue()));
       quote = quote.getNext();
      }	
		return true;
    }
};

3、main.java测试主类

package test2;
public class ListTest {
    public static void main(String[] args) {
       
        System.out.println("--------insert test---------");
        List list = new List();
        list.insertToHead(new Node(1));
        list.insert(0, new Node(2));
        list.insert(0,new Node(3));
        list.insert(new Node(4));
        list.insert(2, 5);
        list.insertToHead(new Node(9));
        list.insert(0,new Node(6));
        list.insert(new Node(7));
        list.insert(new Node(8));
        list.printList();

        System.out.println("--------remove test---------");
        list.remove(3);
        list.remove(0);
        list.remove(6);
        list.printList();
    }
}

本文为笔者的java实习作业，欢迎大家讨论指正。