学过了C、C++的链表，Java的链表也大致相同，唯一的区别就是Java中不存在指针的概念，只有引用，那么链表中的每一个节点的内容就是数据域和引用域（存储数据和指向下一个节点的引用）
Java中单链表的实现要先定义节点类、定义链表类（实现添加、删除、插入节点等操作）
节点类：
class="java">
package 链表练习;
public class Node {
private Object data;//数据
private Node next;//引用域
public Object getdata()
{
return data;
}
public void setdata(Object data)
{
this.data=data;
}
public Node getNext()
{
return next;
}
public void setNext(Node next)
{
this.next=next;
}
}
有了节点类，就可以在链表类中实现对节点的插入删除替换等操作
package 链表练习;
public class LinkedList {
private Node root;// 声明一个根节点
private Node tail;// 声明一个尾节点
private int size;// 声明记录链表中节点的个数
/**
* 添加节点的方法
*
* newnode要被添加的节点对象
*/
public void add(Node newnode) {
// 判断root是否为null，如果是，则表示此时第一次添加节点
if (root ==null) {
root = newnode;// 将新节点给根节点
tail = newnode;// 将新节点给尾节点
}
else {// 将新节点添加到尾节点之后。
tail.setNext(newnode);// 将新节点设置为尾节点的下一个节点
tail = newnode;// 将尾节点移动到新添加的节点上，此处表示是末尾节点。
}
size++;// 让计数器加1
}
/**
* 移除指定索引位置的数据
* 在指定位置处删除节点
* 返回移除的数据
*/
public Object removeindex(int index) {
Node node = root;//遍历的节点,从根节点开始遍历
Node removeNode;//要移除的节点
if (index == 0) {//如果要移除的是第一个节点
root = node.getNext();//将root的下一个节点设置为root
removeNode = node;//把原来的root赋给要移除的节点
} else {//如果要移除的是不是第一个节点
//找到要移除节点的前一个节点对象
for (int i = 0; i < index - 1; i++) {
node = node.getNext();
}
//判断要移除的节点是否是最后一个
if (index == size - 1) {
//将node的下一个节点赋给要移除的节点
removeNode = node.getNext();
//将node的下一个节点引用设置为null
node.setNext(null);
} else {//要移除的节点是在链表的中间
//将node的下一个节点赋给要移除的节点
removeNode = node.getNext();
//将removeNode下一个节点的引用赋给nextNode
Node nextNode = removeNode.getNext();
//将removeNode的下一个节点nextNode赋给node,保持链表不会中断
node.setNext(nextNode);
}
}
size--;
//返回要移除节点的数据域对象
return removeNode.getdata();
}
/**
* 获取指定索引位置节点的数据
*
* @param index指定的索引位置
*/
public Object getData(int index) {
if (index < 0 || index >= size)//如果索引位置超出范围
return null;
Node node = root;//定义用来遍历的节点
// 循环获取到指定索引位置的节点
for (int i = 0; i < index; i++) {
node = node.getNext();
}
// System.out.println(node);
// 返回指定索引位置的元素
return node.getdata();
}
/**
* 修改索引节点的数据
* @return
*/
public Object changedata(int index ,Object data)
{
if(index<0||index>=size)
return null;//如果索引位置超出范围，返回空
Node node=root;
for(int i=0;i<index;i++){
node=node.getNext();
}
node.setdata(data);//改变指定节点的数据
return node.getdata();//返回索引位置的数据
}
/**
* 移除指定的数据,根据对象的属性值来移除数据
* removedata为指定要移除的数据
* 返回移除的次数
*/
public int removeData(Object removedata){
Node node = root;//定义用来遍历的节点
int count=0;
int index;
Node removeNode;
//如果要移除的是头节点
if(root.getdata().equals(removedata))
{root=root.getNext();
count=1;
}
// 循环获取到指定索引位置的节点
for (int i = 0; i < size-2; i++) {
if(node.getNext().getdata().equals(removedata))//如果node的下一节点的数据就是要找的数据,现在node就是要移除数据的前一个指针
{
index=i+1;
count++;
removeNode = node.getNext();//removeNode就是要移除数据的节点
//获取要删除节点的下一个节点，定义为nextNode
Node nextNode = removeNode.getNext();
//将removeNode的下一个节点nextNode赋给node,这样要移除节点的前一个节点就跳过removeNode直接指向nextNode了
node.setNext(nextNode);
}
node = node.getNext();//获取下一节点
}
size=size-count;
return count;//返回移除指定数据的次数
}
/**
* 返回链表中节点总数
*
* @return 返回size属性
*/
public int size() {
return size;
}
/**
*在指定位置插入节点
*index为指定索引位置
*/
public void insert(int index,Object s)
{
if(index<0||index>size)
System.out.println("超出范围重新输入");
Node temp=root;//定义要遍历的节点，从根节点开始遍历
Node insertNode=new Node();//定义要添加的节点
insertNode.setdata(s);
for(int i=0;i<index-1;i++)//得到要原链表添加位置的前一个节点
{
temp=temp.getNext();
}
insertNode.setNext(temp.getNext());
temp.setNext(insertNode);//设置这个节点指向要插入的节点
// Node temp1=new Node();
// temp1=temp.getNext();
// temp.setNext(insertNode);
// insertNode.setNext(temp1);
size++;
}
}
相关文章
