- 浏览: 106190 次
- 性别:
- 来自: 北京
文章分类
- 全部博客 (75)
- JVM (22)
- 数据结构 (11)
- java 基础 (16)
- gc (6)
- jmock (1)
- Google (2)
- MapReduce (1)
- Memory (2)
- 算法 (2)
- cglib (1)
- jdk (3)
- 虚拟机 (3)
- 安全 (2)
- 多线程 (1)
- 工作 (1)
- 生活 (1)
- MongoDB (2)
- Hadoop (4)
- HDFS (2)
- cms (2)
- Spring (1)
- 网络协议 (1)
- GitHub (1)
- MYSQL 调优和使用必读(转) (1)
- 分布式 (2)
- Big Data (0)
- 技术Blog (1)
- Hbase (2)
- Zookeeper (1)
- paper (0)
最新评论
-
lzc_java:
Java线程安全兼谈DCL -
select*from爱:
it's nice
IT业薪水大揭秘
转载自 ---- http://359094247.iteye.com/blog/1613823
链表
链表是一种物理存储单元上非连续非顺序的存储结构。链表有一系列结点组成,每个结点包括两个部分:存储数据元素的数据域,和存储下一个结点地址的指针域(引用)。
链表便于插入和删除操作。
链表的分类:
1、单向链表
单向链表的每个结点右存储数据元素的数据域和指向下一个结点的指针域组成。
Java代码 收藏代码
/**
* 单向链表结点类
*/
public class LinkNode{
private Object obj;//结点内的数据对象
private LinkNode next;//对下一个结点的引用
//构造方法
public LinkNode(Object obj){
this.obj = obj;
}
//得到节点中的数据对象
public Object getObj(){
return obj;
}
//设置节点数据对象
public void setObj(Object obj){
this.obj = obj;
}
//得到子节点
public LinkNode getNext(){
return child;
}
//设置子节点
public void setNext(LinkNode next){
this.child = child;
}
}
2、双向链表
双向链表有一个数据域和两个链域,一个存储直接子结点地址(右链域),一个存储直接父结点地址(左链域)。
Java代码 收藏代码
public class LinkNode {
private Object obj;//结点内的数据对象
private LinkNode child;//对下一个结点的引用
private LinkNode parent;//对上一个结点的引用
//构造方法
public LinkNode(Object obj){
this.obj = obj;
}
//得到节点中的数据对象
public Object getObj(){
return obj;
}
//设置节点中的数据对象
public void setObj(Object obj){
this.obj = obj;
}
//得到子节点
public LinkNode getChild(){
return child;
}
//设置子节点
public void setChild(LinkNode child){
this.child = child;
}
//得到父节点
public LinkNode getParent(){
return parent;
}
//设置父节点
public void setParent(LinkNode parent){
this.parent = parent;
}
}
使用链表实现数据的查找、插入、删除等操作。
Java代码 收藏代码
public class LinkTest {
//设置链表的头结点为空
private static LinkNode front = null;
//设置链表的尾结点为空
private static LinkNode last = null;
/**
* 主方法
* @param args
*/
public static void main(String[] args){
LinkTest linktest = new LinkTest();
//实例化员工对象
Worker wk1 = new Worker("张三","0001",3500);
Worker wk2 = new Worker("李四","0009",3000);
Worker wk3 = new Worker("王五","0006",5000);
Worker wk4 = new Worker("熊哥","0003",3500);
Worker wk5 = new Worker("王麻子","0007",4000);
//将员工对象加入到链表中
linktest.add(wk1);
linktest.add(wk2);
linktest.add(wk3);
linktest.add(wk4);
linktest.print(front);
//在下标为2的位置插入新结点
linktest.insert(2, wk5);
linktest.print(front);
// //删除下标为3的位置的结点
// linktest.delete(3);
// linktest.print(front);
//按指定顺序输出
linktest.inOrder();
}
/**
* 向链表中加入结点,从链表末尾添加
* @param obj
*/
public void add(Object obj){
LinkNode node = new LinkNode(obj);
if(front==null){//如果链表为空
front = node;
last = front;
}else{//如果链表不为空
last.setChild(node);
node.setParent(last);
last = node;
}
}
/**
* 在指定索引位置插入结点,索引是从0开始的
* @param index 要插入的索引位置
* @param obj
*/
public void insert(int index,Object obj){
//实例化一个新的结点
LinkNode newNode = new LinkNode(obj);
LinkNode temp = front;
for(int i=0;i<index-1;i++){
temp = temp.getChild();
}
//循环结束后的temp是索引位置的前一个结点
//设置新节点的子结点是索引位置结点,索引位置结点的父结点是新结点
(temp.getChild()).setParent(newNode);
newNode.setChild(temp.getChild());
//设置索引位置前一个结点的子结点是新结点,新结点的父结点是该结点
temp.setChild(newNode);
newNode.setParent(temp);
}
/**
* 删除索引位置的结点
* @param index
*/
public void delete(int index){
if(index>=0&&index<this.getLength()){
LinkNode node = this.getLinkNode(index);
if(node.getChild()==null){
node.getParent().setChild(null);
}
if(node.getParent()==null){
node.getChild().setParent(null);
front = node.getChild();
}
if(node.getParent()!=null&&node.getChild()!=null){
(node.getParent()).setChild(node.getChild());
(node.getChild()).setParent(node.getParent());
}
}
}
/**
* 得到索引位置的结点
* @param index 索引位置
* @return 返回的是一个结点
*/
public LinkNode getLinkNode(int index){
if(index>=0&&index<this.getLength()){
int number = 0;
LinkNode node = front;
while(number!=index){
node = node.getChild();
number++;
}
// System.out.println("\t"+node.getObj());
return node;
}else{
System.out.println("下标越界");
return null;
}
}
/**
* 得到链表的长度
* @return
*/
public int getLength(){
int count = 0;
LinkNode node = front;
while(node!=null){
count++;
node = node.getChild();
}
return count;
}
/**
* 根据员工工资非降序排列员工对象并输出
*/
public void inOrder(){
//整型数组用来存储员工工资
int[] a = new int[this.getLength()];
//Object数组用来存储员工对象
Object[] moneyOrder = new Object[this.getLength()];
//循环遍历两个数组,将员工工资和员工对象分别存储到两个数组中的相应下标位置
for(int i=0;i<this.getLength();i++){
a[i] = ((Worker) this.getLinkNode(i).getObj()).getMoney();
moneyOrder[i] = this.getLinkNode(i).getObj();
}
//使用冒泡排序法,对员工工资大小进行非降序排列,然后将员工对象数组也对应调整,
//总终员工对象数组的排列是按照其工资的非降序排列的
for(int i=0;i<a.length-1;i++){
for(int j=0;j<a.length-i-1;j++){
if(a[j]>a[j+1]){
//调整工资数组
int temp = a[j];
a[j] = a[j+1];
a[j+1] = temp;
//调整员工对象数组
Object txt = moneyOrder[j];
moneyOrder[j] = moneyOrder[j+1];
moneyOrder[j+1] = txt; }
}
}
//输出工资数组
for(int i=0;i<a.length;i++){
System.out.println(a[i]);
}
//输出员工对象数组-----它是按照工资的非降序排列的员工对象
for(int i=0;i<a.length;i++){
System.out.println(moneyOrder[i].toString());
}
}
/**
* 打印链表中的数据内容
* @param root
*/
public void print(LinkNode root){
if(root!=null){
Object data = root.getObj();
System.out.println(data);
LinkNode temp = root.getChild();
print(temp);
}
}
}
Java代码 收藏代码
/**
* 员工类
* @author 客
*
*/
public class Worker {
private String name;
private String number;
private int money;
/**
* 构造方法
* @param name 员工姓名
* @param number 员工工号
* @param money 员工工资
*/
public Worker(String name,String number,int money){
this.name = name;
this.number = number;
this.money = money;
}
public void setName(String name){
this.name = name;
}
public String getName(){
return name;
}
public void setNumber(String number){
this.number = number;
}
public String getNumber(){
return number;
}
public void setMoney(int money){
this.money = money;
}
public int getMoney(){
return money;
}
public String toString(){
return name+"的工号是:"+number+"\t工资是:"+money;
}
}
3、循环链表
将末尾结点指向根结点。
如有不足欢迎指正!
链表
链表是一种物理存储单元上非连续非顺序的存储结构。链表有一系列结点组成,每个结点包括两个部分:存储数据元素的数据域,和存储下一个结点地址的指针域(引用)。
链表便于插入和删除操作。
链表的分类:
1、单向链表
单向链表的每个结点右存储数据元素的数据域和指向下一个结点的指针域组成。
Java代码 收藏代码
/**
* 单向链表结点类
*/
public class LinkNode{
private Object obj;//结点内的数据对象
private LinkNode next;//对下一个结点的引用
//构造方法
public LinkNode(Object obj){
this.obj = obj;
}
//得到节点中的数据对象
public Object getObj(){
return obj;
}
//设置节点数据对象
public void setObj(Object obj){
this.obj = obj;
}
//得到子节点
public LinkNode getNext(){
return child;
}
//设置子节点
public void setNext(LinkNode next){
this.child = child;
}
}
2、双向链表
双向链表有一个数据域和两个链域,一个存储直接子结点地址(右链域),一个存储直接父结点地址(左链域)。
Java代码 收藏代码
public class LinkNode {
private Object obj;//结点内的数据对象
private LinkNode child;//对下一个结点的引用
private LinkNode parent;//对上一个结点的引用
//构造方法
public LinkNode(Object obj){
this.obj = obj;
}
//得到节点中的数据对象
public Object getObj(){
return obj;
}
//设置节点中的数据对象
public void setObj(Object obj){
this.obj = obj;
}
//得到子节点
public LinkNode getChild(){
return child;
}
//设置子节点
public void setChild(LinkNode child){
this.child = child;
}
//得到父节点
public LinkNode getParent(){
return parent;
}
//设置父节点
public void setParent(LinkNode parent){
this.parent = parent;
}
}
使用链表实现数据的查找、插入、删除等操作。
Java代码 收藏代码
public class LinkTest {
//设置链表的头结点为空
private static LinkNode front = null;
//设置链表的尾结点为空
private static LinkNode last = null;
/**
* 主方法
* @param args
*/
public static void main(String[] args){
LinkTest linktest = new LinkTest();
//实例化员工对象
Worker wk1 = new Worker("张三","0001",3500);
Worker wk2 = new Worker("李四","0009",3000);
Worker wk3 = new Worker("王五","0006",5000);
Worker wk4 = new Worker("熊哥","0003",3500);
Worker wk5 = new Worker("王麻子","0007",4000);
//将员工对象加入到链表中
linktest.add(wk1);
linktest.add(wk2);
linktest.add(wk3);
linktest.add(wk4);
linktest.print(front);
//在下标为2的位置插入新结点
linktest.insert(2, wk5);
linktest.print(front);
// //删除下标为3的位置的结点
// linktest.delete(3);
// linktest.print(front);
//按指定顺序输出
linktest.inOrder();
}
/**
* 向链表中加入结点,从链表末尾添加
* @param obj
*/
public void add(Object obj){
LinkNode node = new LinkNode(obj);
if(front==null){//如果链表为空
front = node;
last = front;
}else{//如果链表不为空
last.setChild(node);
node.setParent(last);
last = node;
}
}
/**
* 在指定索引位置插入结点,索引是从0开始的
* @param index 要插入的索引位置
* @param obj
*/
public void insert(int index,Object obj){
//实例化一个新的结点
LinkNode newNode = new LinkNode(obj);
LinkNode temp = front;
for(int i=0;i<index-1;i++){
temp = temp.getChild();
}
//循环结束后的temp是索引位置的前一个结点
//设置新节点的子结点是索引位置结点,索引位置结点的父结点是新结点
(temp.getChild()).setParent(newNode);
newNode.setChild(temp.getChild());
//设置索引位置前一个结点的子结点是新结点,新结点的父结点是该结点
temp.setChild(newNode);
newNode.setParent(temp);
}
/**
* 删除索引位置的结点
* @param index
*/
public void delete(int index){
if(index>=0&&index<this.getLength()){
LinkNode node = this.getLinkNode(index);
if(node.getChild()==null){
node.getParent().setChild(null);
}
if(node.getParent()==null){
node.getChild().setParent(null);
front = node.getChild();
}
if(node.getParent()!=null&&node.getChild()!=null){
(node.getParent()).setChild(node.getChild());
(node.getChild()).setParent(node.getParent());
}
}
}
/**
* 得到索引位置的结点
* @param index 索引位置
* @return 返回的是一个结点
*/
public LinkNode getLinkNode(int index){
if(index>=0&&index<this.getLength()){
int number = 0;
LinkNode node = front;
while(number!=index){
node = node.getChild();
number++;
}
// System.out.println("\t"+node.getObj());
return node;
}else{
System.out.println("下标越界");
return null;
}
}
/**
* 得到链表的长度
* @return
*/
public int getLength(){
int count = 0;
LinkNode node = front;
while(node!=null){
count++;
node = node.getChild();
}
return count;
}
/**
* 根据员工工资非降序排列员工对象并输出
*/
public void inOrder(){
//整型数组用来存储员工工资
int[] a = new int[this.getLength()];
//Object数组用来存储员工对象
Object[] moneyOrder = new Object[this.getLength()];
//循环遍历两个数组,将员工工资和员工对象分别存储到两个数组中的相应下标位置
for(int i=0;i<this.getLength();i++){
a[i] = ((Worker) this.getLinkNode(i).getObj()).getMoney();
moneyOrder[i] = this.getLinkNode(i).getObj();
}
//使用冒泡排序法,对员工工资大小进行非降序排列,然后将员工对象数组也对应调整,
//总终员工对象数组的排列是按照其工资的非降序排列的
for(int i=0;i<a.length-1;i++){
for(int j=0;j<a.length-i-1;j++){
if(a[j]>a[j+1]){
//调整工资数组
int temp = a[j];
a[j] = a[j+1];
a[j+1] = temp;
//调整员工对象数组
Object txt = moneyOrder[j];
moneyOrder[j] = moneyOrder[j+1];
moneyOrder[j+1] = txt; }
}
}
//输出工资数组
for(int i=0;i<a.length;i++){
System.out.println(a[i]);
}
//输出员工对象数组-----它是按照工资的非降序排列的员工对象
for(int i=0;i<a.length;i++){
System.out.println(moneyOrder[i].toString());
}
}
/**
* 打印链表中的数据内容
* @param root
*/
public void print(LinkNode root){
if(root!=null){
Object data = root.getObj();
System.out.println(data);
LinkNode temp = root.getChild();
print(temp);
}
}
}
Java代码 收藏代码
/**
* 员工类
* @author 客
*
*/
public class Worker {
private String name;
private String number;
private int money;
/**
* 构造方法
* @param name 员工姓名
* @param number 员工工号
* @param money 员工工资
*/
public Worker(String name,String number,int money){
this.name = name;
this.number = number;
this.money = money;
}
public void setName(String name){
this.name = name;
}
public String getName(){
return name;
}
public void setNumber(String number){
this.number = number;
}
public String getNumber(){
return number;
}
public void setMoney(int money){
this.money = money;
}
public int getMoney(){
return money;
}
public String toString(){
return name+"的工号是:"+number+"\t工资是:"+money;
}
}
3、循环链表
将末尾结点指向根结点。
如有不足欢迎指正!
发表评论
-
哈希表
2013-05-03 11:03 1593转载自 ---- http://blog.java ... -
哈夫曼与压缩
2013-01-18 15:24 874转载自 ---- http://359094247.iteye ... -
排序算法java版(转载)
2011-08-10 14:06 859转载自 ---- http://yiyickf.iteye.c ... -
(转)B树、B-树、B+树、B*树都是什么
2011-08-03 16:55 671B 树 即二叉搜 ... -
(转)深入研究B树索引(五)续
2011-08-03 16:53 8415.3 重建 B 树索引对于查询性能的影响 ... -
(转)深入研究B树索引(五)
2011-08-03 16:53 8685. 重建 ... -
(转)深入研究B树索引(四)续
2011-08-03 16:52 7774.2 B 树索引的 ... -
(转)深入研究B树索引(三、四)
2011-08-03 16:51 7563. B 树索引的访问 ... -
(转)深入研究B树索引(二)
2011-08-03 16:51 9002. B 树索引的 ... -
(转)深入研究B树索引(一)
2011-08-03 16:50 1036摘要: 本文对B 树索引的结构、内部管理等方面做了一个 ...
相关推荐
java 链表心得,对于感到困难的朋友会有很大帮助,与其他语言互通
用java链表实现了两个多项式的相加、相乘,最后得到最终结果以链表形式输出
JAVA链表实现类(数据结构学习).chm
java链表,非常易于理解,能帮助你快速掌握链表编程
本资料实例讲解java单项链表的实现以及拓展进行排序,每行代码都附有注释
链表实验JAVA 源代码 压缩包分三个文件ListNode.java,StringLinkedList.java,StringLinkedList.java
java中链表的创建 使用 实例 。初学者用于理解链表的使用。带有60%带有注释。 java链表 链表的讲解 java源代码加注释
Java链表
java考试复习用,顺手写了一个。zip
和文章的Java链表相匹配,里面的步骤都分级了,可以按照步骤写就可以实现java链表的增删改查等操作第一次制作可能有些简陋,但是还是挺清晰的,刚学的可以看一下,这个也是我刚学的时候写的笔记,比较通俗易懂都是...
Java 数据结构 链表 Java链表 数据结构链表
约瑟夫问题,通过类实现的链表,并加以改进,做成双向链表
JAVA链表的介绍(包含单项链表、双向链表)、LinkedList 与 ArrayList 比较、链表的基本操作、基本方法等
java语言 数据结构 单链表的实现
分享一下学习java链表的一些笔记新的!
Java链表实现三例绝对经典
基于Java链表实现的字典树(trie),实现了增删改查等功能,它说摘要必须大于50字我还能说啥啥啥啥
链表可以作为语言爱好者研究一哈
Amazon 面试题,如何用O(N)实现在链表中找出 是否出现循环(Loop),算法也可以用在其他语言(C,C++等)
基于java 的 链表完成的 多项式相加