Java 实现单链表代码,Java代码库,德仔网

代码语言

代码分类

【Java】 Java 实现单链表

作者:空云万里晴 / 发布于2012/11/26/ 753

package com.llist;

public interface LList<T> {
	
	boolean isEmpty();			// 判断线性表是否为空
	int length();				// 返回线性表长度
	T get(int i);				// 返回第i(i>0)个元素
	void set(int i,T x);		// 设置第i个元素的值为x
	void insert(int i,T x);		// 插入x作为第i个元素
	void append(T x);			// 在线性表最后插入x元素
	T remove(int i);			// 删除第i个元素并返回被删对象
	void removeAll();			// 删除线性表所有元素
	int Search(T key);			// 查找，返回首次出现关键子为key的元素序号
	
}


package com.llist;

public class Node<T> {
	
	public T data;		  // 数据域，保存数据元素
	public Node<T> next;	// 地址域，保存后继结点
	
	public Node(){
	}
	
	public Node(T data,Node<T> next){
		this.data = data;
		this.next = next;
	}
	
}

package com.llist;

public class SingleLinkList<T> implements LList<T> {
	
	protected Node<T> head;	   // 头指针，指向单链表的头结点
	
	// 默认构造方法，构造空单链表
	public SingleLinkList(){			
		head = new Node<T>();
	}
	
	// 由指定数组中的多个对象构造单链表，采用尾查构造单链表
	public SingleLinkList(T[] element){
		this();
		Node<T> rear = this.head;
		for(int i=0;i<element.length;i++){
			rear.next = new Node<T>(element[i],null);
			rear = rear.next;
		}
	}
	
	// 判断链表是否为空
	public boolean isEmpty() {
		return this.head.next==null;
	}

	// 返回链表的长度
	public int length() {
		int  count = 0;
		Node<T> p = this.head.next;
		while(p!=null){
			count++;
			p = p.next;
		}
		return count;
	}

	// 返回第i(i>0)个元素，若i的指定序号无效，则返回null
	public T get(int i) {
		if(i<=0||i>this.length()){
			return null;
		}
		else{
			Node<T> p = this.head;
			for(int j=0;j<i;j++){
				p = p.next;
			}
			return p.data;
		}
	}

	// 设置第i(i>0)个元素的值为x，若i指定序号无效，则抛出序号越界异常
	public void set(int i, T x) {
		if(x==null)
			return;
		if(i<=0||i>this.length()){
			// 抛出序号越界异常
			throw new IndexOutOfBoundsException("指定序号i="+i+"越界！");	
		}
		else{
			Node<T> p = this.head;
			for(int j=0;j<i;j++){
				p = p.next;
			}
			p.data = x;
		}
		
	}

	// 链表的插入操作
	public void insert(int i, T x) {
		if(x==null)		// 插入对象不能为空
			return;
		if(i==0){		// 插在头结点之后
			head.next = new Node<T>(x,this.head.next);
		}
		else if(i>0&&i<=this.length()){
			Node<T> p = this.head;
			// 寻找插入位置
			for(int j=0;j<i;j++){			
				p = p.next;					
			}
			// 插入x作为p结点的后继结点
			p.next = new Node<T>(x,p.next); 
		}
		else{
			// 抛出序号越界异常
			throw new IndexOutOfBoundsException("指定序号i="+i+"越界！");	
		}
		
	}

	// 在单链表的最后添加对象
	public void append(T x) {
		insert(this.length(),x);
	}

	// 删除序号为i的结点，操作成功返回给对象，否则返回null
	public T remove(int i) {
		if(i<=0||i>this.length()){
			return null;
		}
		else{
			Node<T> p = this.head;
			// 定位到待删除结点(i)的前驱结点(i-1)
			for(int j=0;j<i-1;j++){		
				p = p.next;					
			}
			T old = p.next.data;
			p.next = p.next.next;
			return old;
		}
	}

	// 删除单链表的所有元素
	public void removeAll() {
		this.head.next = null;
	}

	// 查找，返回首次出现关键子key的元素的序号
	public int Search(T key) {
		if(key==null)
			return 0;
		else{
			int i = 0;
			Node<T> p = this.head;
			while(p.next!=null){
				i++;
				p = p.next;
				if(p.data.equals(key))
					break;
			}
			if(p.next==null)
				return 0;
			else
				return i;
		}
	}
	
	//返回链表的所有元素的描述字符串，覆盖Object类的toString()方法
	public String toString(){
		String str = " ( ";
		Node<T> p = this.head.next;
		while(p!=null){
			str += p.data.toString();
			p = p.next;
			if(p!=null)
				str += ",";
		}
		str += " ) ";
		return str;
	}
	
}

评论列表

本站所提供的代码，版权归原作者所有，若有侵犯作者版权，请与我们联系，我们将立即删除或修改。谢谢!
本站所有代码发布及提供者。

试试其它关键字

　单链表　

同语言下

可能有用的

空云万里晴贡献的其它代码(5)