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();
}
}
操作什么的就自己想吧,哈哈哈
分享到:
相关推荐
NULL 博文链接:https://langyu.iteye.com/blog/1167581
java知识拾遗--三大框架的技术起源.pdfjava知识拾遗--三大框架的技术起源.pdf
Struts、Hibernate和Spring是我们Java开发中的常用的框架,他们分别针对不同的应用场景给出最合适的解决方案。但你是否知道,这些知名框架最初是怎样产生的?
java知识拾遗--三大框架的技术起源.docxjava知识拾遗--三大框架的技术起源.docx
在学习Java过程中,自己收集了很多的Java的学习资料,分享给大家,有需要的欢迎下载,希望对大家有用,一起学习,一起进步。
11.java基础拾遗--匿名内部类语法详解.mp4
09.java基础拾遗--类的加载和对象的构造过程.mp4
10.java基础拾遗--匿名内部类的应用--实现scala中的集合map方法.mp4
Java语言拾遗 │ │ └─util 工具类 │ └─mq 消息队列 │ └─kafka └─resources 消息队列源码会作专题研究 关于消息队列使用参考另一个库:https://github.com/GitJavaProgramming/springboot_mybatis 参考...
17. 拾遗物品登记表.pdf
拾遗·椰雕.css
Java学习笔记 入门准备 接触物件 物件向导 资源管理 物件容器 输入输出 執行緒 反射 metadata 资料库 拾遗补缺 视窗程式 参考资料
小学语文教学点滴拾遗
拾遗物品的处理.doc
初中语文文摘社会西游拾遗
24拓展 3:拾遗补漏 —— 再谈分布式锁(1)
常见iphone面试题及答案拾遗,对于面试ios的你肯定会有帮助的。
奥数拾遗201812171