java拾遗录3

主题：java与链表不能不说的秘密

一、关于单向链表

关于链表和数组的讨论，是所有数据结构中所必提的，java自己封装了一些集合类，我们自己不需要去创建什么链表，但是作为一个基本能力，大家还是要有所了解的，下面的代码就是一个简单的单向链表，至于其他类型的链表将在后面一一展示出来。

 

创建节点类

/**
 *@作者  qy
 *@时间版本  版本1 下午04:53:15 2011-8-29
 */
public class Node
{
	public Node next;
	public  Object value;
	public Node(Object value,Node next)
	{
		this.value = value;
		this.next = next;
	}
	@Override
	public String toString()
	{
		return value.toString();
	}
	@Override
	public boolean equals(Object obj)
	{
		return obj.toString().equals(value.toString());
	}
}

 

创建链表 实现增删改查 功能

 

package array;
/**
 *@作者  qy
 *@时间版本  版本1 下午04:56:46 2011-8-29
 */
public class NodeToTest
{
	public Node head;
	/**
	 * 初始化链表
	 * 用对象数组遍历创建
	 * @param objects
	 */
	
	public NodeToTest(Object[] objects)
	{
		
		for (int i = objects.length-1; i >= 0; i--)
		{
			head = new Node(objects[i], head);
		}
	}
	//空构造
	public NodeToTest()
	{
	}
	
	//首端插入
	public void insertByFrist(Node newNode)
	{
		head = new Node(newNode, head);
	}
	
	//尾端插入
	public void insertByLast(Node newNode)
	{
		if(head == null)
		{
			head = newNode;
		}
		else 
		{
			Node temp = head;
			while(temp.next != null)
			{
				temp = temp.next;
			}
			temp.next = newNode;
		}
	}
	
	
	//按照项数删除 删除头项数为0
	public void deleteByIndex(int index)
	{
		Node temp = head;
		if (head == null)
		{
			System.out.println("链表为空");
			return;
		}
		if(index == 0)
		{
			head = head.next;
			return;
		}
		while(temp.next != null)
		{
			if(index == 1)
			{
				temp.next = temp.next.next;
				return ;
			}
			temp = temp.next;
			index--;
		}
	}
	
	//按照对象删除
	public void deleteByValue(Node deleteNode)
	{
		Node temp = head;
		if (head == null)
		{
			System.out.println("链表为空");
			return;
		}
		if(head.equals(deleteNode))
		{
			head = head.next;
			return;
		}
		while(temp.next != null)
		{
			if (temp.next.equals(deleteNode) )
			{
				temp.next = temp.next.next;
				return;
			}
			temp = temp.next;
		}
	}
	
	//插入
	public void insertByIndex(int index,Node newNode)
	{
		if(index == 0||head == null)
		{
			this.insertByFrist(newNode);
		}
		else 
		{
			Node temp = head;
			while(temp != null)
			{
				if(index == 1)
				{
					newNode.next = temp.next;
					temp.next = newNode;
					return;
				}
				temp = temp.next;
				index--;
			}
		}
	}
	
	//返回链表大小
	public int size()
	{
		Node temp = head;
		int i = 0;
		while(temp != null)
		{
			i++;
			temp = temp.next;
		}
		return i;
	}
	
	//方便显示当前链表的内容
	@Override
	public String toString()
	{
		String string = "{";
		Node temp = head;
		while(temp != null)
		{
			string += "["+temp.value.toString()+"],";
			temp = temp.next;
		}
		return string+"}";
	}
	
}

 

  测试类

 

package test;

import array.Node;
import array.NodeToTest;

/**
 *@作者  qy 
 *@时间版本  版本1 下午05:04:44 2011-8-29
 */
public class Test4array
{
	public static void main(String[] args)
	{
		Integer[] array = {1,2,3,4,5,6};
		NodeToTest nodeToTest = new NodeToTest((Object[])array);
		System.out.println(nodeToTest);
		//插入测试
		Node node = new Node(7, null);
		nodeToTest.insertByFrist(node);
		System.out.println(nodeToTest);
//		nodeToTest.insertByLast(node);
//		System.out.println(nodeToTest);
		
		//删除测试
//		nodeToTest.deleteByIndex(3);
//		System.out.println(nodeToTest);
		nodeToTest.deleteByValue(new Node(2, null));
		System.out.println(nodeToTest);
		//测试按位插入
		nodeToTest.insertByIndex(2, new Node(2, null));
		System.out.println(nodeToTest);
	}
}

 

这些就是简单的一个单向链表。

 

对了，还有特别注意：

很多书上都说：链表在插入删除上要比数组快。这句话在理论上是没错的，但其实这只是理论，删除和插入之前都必须先找到位置，这个花费的时间可不是一点半点，所以........

 

二、带表头的双向链表

链表还有很多形式，譬如带表头的单向链表，双向链表，带表头的双向链表，带尾指针的......不过大部分操作都是一样的，所以来一个带表头的双向链表就好了。

package array;
/**
 *@作者  qy
 *@时间版本  版本1 下午07:11:50 2011-8-30
 */
public class ArrayToTest1
{
	public Node1 head = new Node1();
	public Node1 tail = head;
	public ArrayToTest1(Object[] array)
	{
		for (int i = 0; i < array.length; i++) 
		{
			tail.next = new Node1(array[i],tail,null);
			tail = tail.next;
		}
	}
	public  void showByHead()
	{
		Node1 temp = head;
		while (temp.next != null)
		{
			System.out.println(temp.next.value);
			temp = temp.next;
		}
	}
	
	public  void showByTail()
	{
		Node1 temp = tail;
		while (temp != head)
		{
			System.out.println(temp.value);
			temp = temp.previous;
		}
	}
	public static void main(String[] args)
	{
		Integer[] array = {1,2,3,4,5};
		ArrayToTest1 arrayToTest1 = new ArrayToTest1(array);
		arrayToTest1.showByTail();
	}
	
	
}

 操作什么的就自己想吧，哈哈哈