线性表的链式存储结构之单链表类的实现_Java

时间: 2011-08-20 / 分类: 瞎扯谈 / 浏览次数: / 0个评论 发表评论

在之前的两篇博文——线性表接口的实现_Java线性表的链式存储结构之单链表结点类的实现_Java中,我们实现了线性表的接口和单链表的结点类,今天让我们来实现线性表的链式存储结构——单链表类。

注释写得很详细了,直接看吧:

package dataStructure.linearList;
import dataStructure.linearList.Node;							//导入单链表结点类

public class SinglyLinkedList<E> implements LList<E>			//单链表类,实现线性表接口
{
	protected Node<E> head;										//头指针,指向单链表第一个结点
	
	public SinglyLinkedList()									//构造空单链表
	{
		this.head = null;
	}
	
	public SinglyLinkedList(Node<E> head)						//构造指定头指针的单链表
	{
		this.head = head;
	}
	
	public boolean isEmpty()									//判断单链表是否为空
	{
		return this.head == null;
	}
	
	public int length()											//返回单链表长度,单链表遍历算法
	{
		int i = 0;
		Node<E> p = this.head;
		while(p != null)
		{
			i ++;
			p = p.Next;
		}
		return i;
	}
	
	public E get(int index)										//返回序号为index的对象,若单链表为空或序号错误则返回null
	{
		if(this.head != null && index >= 0)
		{
			int j = 0;
			Node<E> p = this.head;
			while(p != null && j < index)
			{
				j ++;
				p = p.Next;
			}
			if(p !=null)
			{
				return (E)p.Data;
			}
		}
		return null;
	}
	
	public E set(int index,E element)							//设置序号为index的对象为element,若操作成功,返回原对象,否则返回null
	{
		if(this.head != null && index >= 0 && element != null)
		{
			int j = 0;
			Node<E> p = this.head;
			while(p != null && j < index)
			{
				j ++;
				p = p.Next;
			}
			if(p != null)
			{
				E old = (E)p.Data;
				p.Data = element;
				return old;										//若操作成功,则返回原对象
			}
		}
		return null;											//操作不成功
	}
	
	public boolean add(int index,E element)						//插入element对象,插入后对象序号为index,若操作成功返回true
	{
		if(element ==null)
		{
			return false;										//不能添加空对象(null)
		}
		
		if(this.head == null || index <= 0)						//头插入
		{
			Node<E> q = new Node<E>(element);
			q.Next = this.head;
			this.head = q;
			//this.head = new Node(element,this.head);			//头插入,相当于上述3句
		}
		else													//单链表不空且index>=1
		{
			int j = 0;
			Node<E> p = this.head;
			while(p.Next != null && j < index - 1)				//寻找插入位置
			{
				j ++;
				p = p.Next;
			}
			Node<E> q = new Node<E>(element);					//中间/尾插入
			q.Next = p.Next;									//q插入在p结点之后
			p.Next = q;
			//p.Next = new Node(element,p.Next);				//中间/尾插入,相当于上述3句
		}
		return true;
	}
	
	public boolean add(E element)								//在单链表最后插入对象
	{
		return add(Integer.MAX_VALUE,element);
	}
	
	public E remove(int index)									//移去序号为index的对象,若操作成功则返回被移去的对象,否则返回null
	{
		E old = null;
		if(this.head != null && index >= 0)
		{
			if(index == 0)										//头删除
			{
				old = (E)this.head.Data;
				this.head = this.head.Next;
			}
			else												//中间/尾删除
			{
				int j = 0;
				Node<E> p = this.head;
				while(p.Next != null && j < index - 1)			//定位到待删除结点的前驱结点
				{
					j ++;
					p = p.Next;
				}
				if(p.Next != null)
				{
					old = (E)p.Next.Data;						//若操作成功,返回被移去对象
					p.Next = (p.Next).Next;						//删除p的后继结点
				}
			}
		}
		return old;
	}
	
	public void clear()											//清空单链表
	{
		this.head = null;
	}
	
	public String toString()									//返回所有元素值对应的字符串
	{
		String str = "(";
		Node<E> p = this.head;
		while(p != null)
		{
			str += p.Data.toString();
			p = p.Next;
			if(p != null)
			{
				str += ",";
			}
		}
		return str + ")";
	}
}

在下一篇博文中我将和大家讨论有关单链表的toString()的递归算法以及单链表的逆转问题。敬请期待。

您阅读此文共耗时

发表评论

你必须 登录后 才能留言!