Java单链表基本操作的实现

最近被问到链表,是一个朋友和我讨论Java的时候说的。说实话,我学习编程的近一年时间里,学到的东西还是挺少的。语言是学了Java和C#,关于Web的学了一点Html+css+javascript。因为比较偏好,学习WinForm时比较认真,数据库操作也自己有所研究。但链表这个东西我还真没有学习和研究过,加上最近自己在看WPF,而课程也到了JSP了,比较紧。

但是我还是抽了一个晚上加半天的时间看了一下单向链表。并且使用Java试着写了一个实例出来。没有接触过链表的朋友可以作为参考,希望大家多提宝贵意见。

我们首先解释一下什么是链表。就我所知,链表是一种数据结构,和数组同级。比如,Java中我们使用的ArrayList,其实现原理是数组。而LinkedList的实现原理就是链表了。我的老师说,链表在进行循环遍历时效率不高,但是插入和删除时优势明显。那么他有着愈十年的编程经验,我是相信的。不过不知道他是否是说双向链表,我们在此呢只对单向链表做一个了解。

链表(Chain本文所说链表均为单向链表,以下均简称单向链表)实际上是由节点(Node)组成的,一个链表拥有不定数量的节点。而向外暴露的只有一个头节点(Head),我们对链表的所有操作,都是直接或者间接地通过其头节点来进行的。

节点(Node)是由一个需要储存的对象及对下一个节点的引用组成的。也就是说,节点拥有两个成员:储存的对象、对下一个节点的引用。

  这样说可能大家不是很明白,我贴一张图大家可能更容易理解。

Java单链表基本操作的实现关键代码如下所示:

package com.tyxh.link;
//节点类
public class Node {
protected Node next; //指针域
protected int data;//数据域
public Node( int data) {
this. data = data;
}
//显示此节点
public void display() {
System. out.print( data + " ");
}
}
package com.tyxh.link;
//单链表
public class LinkList {
public Node first; // 定义一个头结点
private int pos = 0;// 节点的位置
public LinkList() {
this. first = null;
}
// 插入一个头节点
public void addFirstNode( int data) {
Node node = new Node(data);
node. next = first;
first = node;
}
// 删除一个头结点,并返回头结点
public Node deleteFirstNode() {
Node tempNode = first;
first = tempNode. next;
return tempNode;
}
// 在任意位置插入节点 在index的后面插入
public void add(int index, int data) {
Node node = new Node(data);
Node current = first;
Node previous = first;
while ( pos != index) {
previous = current;
current = current. next;
pos++;
}
node. next = current;
previous. next = node;
pos = 0;
}
// 删除任意位置的节点
public Node deleteByPos( int index) {
Node current = first;
Node previous = first;
while ( pos != index) {
pos++;
previous = current;
current = current. next;
}
if(current == first) {
first = first. next;
} else {
pos = 0;
previous. next = current. next;
}
return current;
}
// 根据节点的data删除节点(仅仅删除第一个)
public Node deleteByData( int data) {
Node current = first;
Node previous = first; //记住上一个节点
while (current. data != data) {
if (current. next == null) {
return null;
}
previous = current;
current = current. next;
}
if(current == first) {
first = first. next;
} else {
previous. next = current. next;
}
return current;
}
// 显示出所有的节点信息
public void displayAllNodes() {
Node current = first;
while (current != null) {
current.display();
current = current. next;
}
System. out.println();
}
// 根据位置查找节点信息
public Node findByPos( int index) {
Node current = first;
if ( pos != index) {
current = current. next;
pos++;
}
return current;
}
// 根据数据查找节点信息
public Node findByData( int data) {
Node current = first;
while (current. data != data) {
if (current. next == null)
return null;
current = current. next;
}
return current;
}
}
package com.tyxh.link;
//测试类
public class TestLinkList {
public static void main(String[] args) {
LinkList linkList = new LinkList();
linkList.addFirstNode(20);
linkList.addFirstNode(21);
linkList.addFirstNode(19);
//19,21,20
linkList.add(1, 22); //19,22,21,20
linkList.add(2, 23); //19,22,23,21,20
linkList.add(3, 99); //19,22,23,99,21,20
linkList.displayAllNodes();
// Node node = linkList.deleteFirstNode();
// System.out.println("node : " + node.data);
// linkList.displayAllNodes();
// node = linkList.deleteByPos(2);
// System.out.println("node : " + node.data);
// linkList.displayAllNodes();
// linkList.deleteFirstNode();
Node node = linkList.deleteByData(19);
// Node node = linkList.deleteByPos(0);
System. out.println( "node : " + node. data);
linkList.displayAllNodes();
Node node1 = linkList.findByPos(0);
System. out.println( "node1: " + node1. data);
Node node2 = linkList.findByData(22);
System. out.println( "node2: " + node2. data);
}
}

以上所述是小编给大家介绍的Java单链表基本操作的实现,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对我们网站的支持!

时间: 2016-07-04

Java实现单链表翻转实例代码

Java实现单链表反转,递归和非递归两种形式 /** * 反转单链表 */ /** * 定义链表 * * @author 16026 * */ class Node { int val; Node next; public Node(int val) { this.val = val; } } public class ReverseList { /** * 反转链表 * * @param head * @return */ public static Node reverseList(Node

Java单链表的实现代码

下面是小编给大家分享的一个使用java写单链表,有问题欢迎给我留言哦. 首先定义一个Node类 public class Node { protected Node next; //指针域 public int data;//数据域 public Node( int data) { this. data = data; } //显示此节点 public void display() { System. out.print( data + " "); } } 接下来定义一个单链表,并实现

Java 数据结构链表操作实现代码

链表是一种复杂的数据结构,其数据之间的相互关系使链表分成三种:单链表.循环链表.双向链表,下面将逐一介绍.链表在数据结构中是基础,也是重要的知识点,这里讲下Java 中链表的实现, JAVA 链表操作:单链表和双链表 主要讲述几点: 一.链表的简介 二.链表实现原理和必要性 三.单链表示例 四.双链表示例 一.链表的简介 链表是一种比较常用的数据结构,链表虽然保存比较复杂,但是在查询时候比较便捷,在多种计算机语言都相应的应用,链表有多种类别,文章针对单链表和双链表进行分析.链表中数据就像被一个链

java 中链表的定义与使用方法

java 中链表的定义与使用方法 Java实现链表主要依靠引用传递,引用可以理解为地址,链表的遍历多使用递归,这里我存在一个疑问同一个类的不同对象的的相同方法的方法内调用算不算递归. 这里我写的是单向链表; 实例代码: package com.example.java; public class MyLink { public static void main(String [] args){ Link l=new Link(); mytype[] la; mytype dsome=new my

Java编程删除链表中重复的节点问题解决思路及源码分享

一. 题目 在一个排序的链表中,存在重复的结点,请删除该链表中重复的结点,重复的结点不保留,返回链表头指针. 二. 例子 输入链表:1->2->3->3->4->4->5 处理后为:1->2->5 三. 思路 个人感觉这题关键是注意指针的指向,可以定义一个first对象(值为-1,主要用于返回操作后的链表),first.next指向head,定义一个last同样指向first(主要用于操作记录要删除节点的前一个节点),定义一个p指向head,指向当前节点.

实现php删除链表中重复的结点

删除链表中重复的结点: 定义两个指针pre和current 两个指针同时往后移动,current指针如果与后一个结点值相同,就独自往前走直到没有相等的 pre指针next直接指向current指针的后一个,把相同的都跳过 pre=linkList current=linkList while current!=null if current->data==current->next->data value=current->data while value==current->

Flex中TabNavigator设置Tabs样式思路及源码

1.设计思路 (1)设计一个TabNavigator,其中包含两个Tabs: (2)设置Tabs样式 2.设计源码 Tabs.mxml: 复制代码 代码如下: <?xml version="1.0" encoding="utf-8"?> <s:Application xmlns:fx="http://ns.adobe.com/mxml/2009" xmlns:s="library://ns.adobe.com/flex

java中使用双向链表实现贪吃蛇程序源码分享

使用双向链表实现贪吃蛇程序 1.链表节点定义: package snake; public class SnakeNode { private int x; private int y; private SnakeNode next; private SnakeNode ahead; public SnakeNode() { } public SnakeNode(int x, int y) { super(); this.x = x; this.y = y; } public int getX(

jquery删除数组中重复元素

话不多说,下面就跟着小编来看下利用jquery实现删除数组中重复元素的具体思路吧 首先定义如下数组: var arr=[0,2,3,5,6,9,2]; 我们可以看到数组中存在重复元素'2'; 最后通过jquery筛选应该得到[0,2,3,5,6,9]; ok,首先我们再定义一个空数组,用来存放最后筛选出来的元素: var new_arr=[]; 利用jquery的$.inArray可以轻松实现: 遍历数组元素: for(var i=0;i<arr.length;i++) { var items=

java 数据结构之删除链表中的元素实例代码

java 删除链表中的元素 以下实例演示了使用 Clear() 方法来删除链表中的元素: import java.util.*; public class Main { public static void main(String[] args) { LinkedList<String> lList = new LinkedList<String>(); lList.add("1"); lList.add("8"); lList.add(&q

Java替换int数组中重复数据的方法示例

本文实例讲述了Java替换int数组中重复数据的方法.分享给大家供大家参考,具体如下: package test; import java.util.HashSet; public class TestList { /** * 根据传递过来的参数过滤掉重复数据 * @param number:需要过滤掉的数据 * @return:筛选好的新数组 */ public static int[] Filter(int[] number){ HashSet<Integer> hs=new HashSe

Java编程—在测试中考虑多态

面向对象编程有三大特性:封装.继承.多态. 封装隐藏了类的内部实现机制,可以在不影响使用的情况下改变类的内部结构,同时也保护了数据.对外界而已它的内部细节是隐藏的,暴露给外界的只是它的访问方法. 继承是为了重用父类代码.两个类若存在IS-A的关系就可以使用继承.,同时继承也为实现多态做了铺垫.那么什么是多态呢?多态的实现机制又是什么?请看我一一为你揭开: 所谓多态就是指程序中定义的引用变量所指向的具体类型和通过该引用变量发出的方法调用在编程时并不确定,而是在程序运行期间才确定,即一个引用变量倒底

python如何删除文件中重复的字段

本文实例为大家分享了python如何删除文件中重复字段的具体代码,供大家参考,具体内容如下 原文件内容放在list中,新文件内容按行查找,如果没有出现在list中则写入第三个文件中. import csv filetxt1 = 'E:/gg/log/log1.txt' filecsv1 = 'E:/gg/log/log1.csv' filecsv2 = 'E:/gg/log/log2.csv' filecsv3 = 'E:/gg/log/log3.csv' class operFileCsv()

python/golang 删除链表中的元素

先用使用常规方法,两个指针: golang实现: type Node struct { value int next *Node } type Link struct { head *Node tail *Node lenth int } // 向链表中添加元素 func (link *Link) add(v int) { if link.lenth == 0 { // 当前链表是空链表 link.head = &Node{v, nil} link.tail = link.head link.l