线性表的单链表实现_JAVA_编程开发_程序员俱乐部

? ? ? 数据结构和算法是程序的灵魂，基本的数据结构分为：线性结构、树、图。线性结构又分为顺序实现的线性结构和链式实现的线性结构。链式线性结构是非随机存取结构，其get（）、set（）的时间复杂度是O(N)；若已知要插入或删除的节点位置的话，其insert（）、remove（）的时间复杂度为O(1)。否则需要进行遍历操作，这时insert（）、remove（）的时间复杂度为O(N)。

? ? ? ?首次写博客，望各位大牛拍砖来助学习。?

? ? ? ?以下 是单链表的实现代码：

class="java">线性表的抽象数据类型：

package dataStructtion.linear;
/**
 * 线性表的抽象数据类型
 * @author xiucai
 * @param <T>
 */
public interface LList<T> {
	/**
	 * 判断是否为空
	 * @return
	 */
	public boolean isEmpty();
	/**
	 * 返回线性表长度
	 * @return
	 */
	public int length();
	/**
	 * 返回下标为i的元素(i>=0)
	 * @param i
	 * @return
	 */
	public T get(int i);
	/**
	 * 设置下标为i的元素值为t
	 * @param i
	 * @param t
	 */
	public void set(int i,T t);
	/**
	 * 在下标为i的位置插入元素t
	 * @param i
	 * @param t
	 */
	public void insert(int i,T t);
	/**
	 * 在线性表末尾追加元素t
	 * @param t
	 */
	public void append(T t);
	/**
	 * 移除下标为i的元素
	 * @param i
	 * @return
	 */
	public T remove(int i);
	/**
	 * 移除线性表所有元素
	 */
	public void removeAll();
	/**
	 * 查找，返回首次出现的关键字为key的元素
	 * @param t
	 * @return
	 */
	public T search(T t);
	/**
	 * 判断线性表是否包含元素t
	 * @param t
	 * @return
	 */
	public boolean contain(T t);
}


单节点的数据结构：

package dataStructtion.linear;
/**
 * 链表的单个节点 
 * @author xiucai
 * @param <T>
 */
public class Node<T> {
	public Object data;//存放数据
	public Node<T> next;//后继
	//初始化节点
	public Node(Object data,Node<T> next){
		this.data=data;
		this.next=next;
	}
	public Node(){
		this(null,null);
	}
	//重写toString方法，用于输出
	public String toString(){
		return this.data.toString();
	}
	//重写equals方法，用于比较
	public boolean equals(Object data){
		if (this.data==data)
			return true;
		if(data instanceof Node){
			Node<T> node=(Node<T>)data;
			if(this.data==node.data&&this.next==node.next)
				return true;
		}
		return false;
	}
	
}



单链表的实现类：


package dataStructtion.linear;
/**
 * 线性表的单链表表示与实现
 * @author xiucai
 * @param <T>
 */
public class SingleLinkedList<T> implements LList<T> {
	private Node<T> head;//头结点
	private int len;//链表长度
	//初始化单链表
	public SingleLinkedList(){
		head=new Node<T>();
		len=0;
	}
	@Override
	public boolean isEmpty() {
		// TODO Auto-generated method stub
		return len==0;
	}
	//获取单链表的长度
	@Override
	public int length() {
		// TODO Auto-generated method stub
		return len;
	}
	//获取第i下标的元素
	@Override
	public T get(int i) {
		// TODO Auto-generated method stub
		if(i<0||i>this.len)
			throw new IndexOutOfBoundsException(i+"下标越界");
		Node<T> node=this.head.next;
		for(int j=0;node!=null&&j<i;j++){
			node=node.next;
		}
		return (T)node.data;
	}
	//设置第i个元素为t
	@Override
	public void set(int i, T t) {
		// TODO Auto-generated method stub
		if(i<0||i>this.len)
			throw new IndexOutOfBoundsException(i+"下标越界");
		if(t==null)
			return ;
		Node<T> node=this.head;
		for(int j=0;node.next!=null&&j<i;j++){
			node=node.next;
		}
		node.data=t;
	}
	//在第i个位置插入元素t
	@Override
	public void insert(int i, T t) {
		// TODO Auto-generated method stub
		if(i<0||i>this.len)
			throw new IndexOutOfBoundsException(i+"下标越界");
		if(t==null) return ;
		Node<T> node=this.head;
		for(int j=0;node.next!=null&&j<i-1;j++){
			node=node.next;
		}
		Node<T> p=new Node<T>(t,node.next);
		node.next=p;
		len++;
	}
	//在单链表末尾追加元素t
	@Override
	public void append(T t) {
		// TODO Auto-generated method stub
		if(t==null)
			return ;
		Node<T> node=this.head;
		for(int i=0;node.next!=null&&i<this.len;i++){
			node=node.next;
		}
		node.next=new Node<T>(t,null);
		len++;
	}
	//移除第i下标的元素
	@Override
	public T remove(int i) {
		// TODO Auto-generated method stub
		if(i<0||i>this.len)
			throw new IndexOutOfBoundsException(i+"下标越界");
		Node<T> node=this.head;
		for(int j=0;node.next!=null&&j<=i-1;j++){
			node=node.next;
		}
		T t=(T)node.next.data;
		node.next=node.next.next;
		len--;
		return t;
	}
	//清空单链表
	@Override
	public void removeAll() {
		// TODO Auto-generated method stub
		this.head.next=null;
		this.len=0;
	}
	//寻找值为t的元素
	@Override
	public T search(T t) {
		// TODO Auto-generated method stub
		if(t==null) 
			return null;
		Node<T> node=this.head;
		for(int i=0;node.next!=null&&i<this.len;i++){
			if(node.next.data.equals(t))
				return (T)node.next.data;
			node=node.next;
		}
		return null;
	}
	//判断单链表是否包含t元素
	@Override
	public boolean contain(T t) {
		// TODO Auto-generated method stub
		return this.search(t)!=null;
	}
	//重写toString，用于输出
	@Override
	public String toString(){
		Node<T> node=this.head;
		String string="[";
		for(int i=0;node.next!=null&&i<this.len;i++){
			string+=node.next.data+" ";
			node=node.next;
		}
		return string+"]";
 	}
}




此类为测试类：



package dataStructtion.linear;
/**
 * 此类用于测试
 * @author xiucai
 */
public class SingleLinkTest {
	public static void main(String[] args) {
		SingleLinkedList<String> s=new SingleLinkedList<String>();
		s.insert(0, "aaa");
		s.append("bbb");
		System.out.println(s);
		System.out.println(s.length());
		System.out.println(s.search("aaa"));
		System.out.println(s.contain("aaa"));
		for(int i=0;i<s.length();i++){
			System.out.println(s.get(i));
		}
		System.out.println(s.remove(0));
		System.out.println(s);
		
		s.removeAll();
		System.out.println(s.length());
		System.out.println(s);
	}
}

?

• SingleLinkedList.zip (2.6 KB)
• 下载次数: 0