链表本身也是线性表，只不过物理存储上不连续
//线性表接口
public interface List {
//获得线性表长度
public int size();
//判断线性表是否为空
public boolean isEmpty();
//插入元素
public void insert(int index, Object obj) throws Exception;
//删除元素
public void delete(int index) throws Exception;
//获取指定位置的元素
public Object get(int index) throws Exception;
}
Node.java:结点类
//结点类
public class Node {
Object element; //数据域
Node next; //指针域
//头结点的构造方法
public Node(Node nextval) {
this.next = nextval;
}
//非头结点的构造方法
public Node(Object obj, Node nextval) {
this.element = obj;
this.next = nextval;
}
//获得当前结点的指针域
public Node getNext() {
return this.next;
}
//获得当前结点数据域的值
public Object getElement() {
return this.element;
}
//设置当前结点的指针域
public void setNext(Node nextval) {
this.next = nextval;
}
//设置当前结点数据域的值
public void setElement(Object obj) {
this.element = obj;
}
public String toString() {
return this.element.toString();
}
}
LinkList.java:单向链表类(核心代码)
//单向链表类
public class LinkList implements List {
Node head; //头指针
Node current;//当前结点对象
int size;//结点个数
//初始化一个空链表
public LinkList()
{
//初始化头结点，让头指针指向头结点。并且让当前结点对象等于头结点。
this.head = current = new Node(null);
this.size =0;//单向链表，初始长度为零。
}
//定位函数，实现当前操作对象的前一个结点，也就是让当前结点对象定位到要操作结点的前一个结点。
//比如我们要在a2这个节点之前进行插入操作，那就先要把当前节点对象定位到a1这个节点，然后修改a1节点的指针域
public void index(int index) throws Exception
{
if(index <-1 || index > size -1)
{
throw new Exception("参数错误！");
}
//说明在头结点之后操作。
if(index==-1) //因为第一个数据元素结点的下标是0，那么头结点的下标自然就是-1了。
return;
current = head.next;
int j=0;//循环变量
while(current != null&&j<index)
{
current = current.next;
j++;
}
}
@Override
public void delete(int index) throws Exception {
// TODO Auto-generated method stub
//判断链表是否为空
if(isEmpty())
{
throw new Exception("链表为空，无法删除！");
}
if(index <0 ||index >size)
{
throw new Exception("参数错误！");
}
index(index-1);//定位到要操作结点的前一个结点对象。
current.setNext(current.next.next);
size--;
}
@Override
public Object get(int index) throws Exception {
// TODO Auto-generated method stub
if(index <-1 || index >size-1)
{
throw new Exception("参数非法！");
}
index(index);
return current.getElement();
}
@Override
public void insert(int index, Object obj) throws Exception {
// TODO Auto-generated method stub
if(index <0 ||index >size)
{
throw new Exception("参数错误！");
}
index(index-1);//定位到要操作结点的前一个结点对象。
current.setNext(new Node(obj,current.next));
size++;
}
@Override
public boolean isEmpty() {
// TODO Auto-generated method stub
return size==0;
}
@Override
public int size() {
// TODO Auto-generated method stub
return this.size;
}
}
测试代码
public class LinkListTest {
public static void main(String[] args) throws Exception {
LinkList list = new LinkList();
for (int i = 0; i < 10; i++) {
int temp = ((int) (Math.random() * 100)) % 100;
list.insert(i, temp);
System.out.print(temp + " ");
}
list.delete(4);
System.out.println("\n------删除第五个元素之后-------");
for (int i = 0; i < list.size; i++) {
System.out.print(list.get(i) + " ");
}
}
}
测试代码输出
31 98 25 18 10 34 1 20 57 81
------删除第五个元素之后-------
31 98 25 18 34 1 20 57 81
另外一种实现，将节点类Node改为内部类
/**
* 单向链表另外一种实现，将节点类Node改为内部类
*
* @author adminjack
*
*/
public class LinkList2 {
private int size;
private Node root; // 定义一个根节点
private int foot = 0; // 操作返回数组的脚标
private String[] retData; // 返回数组
private boolean changeFlag = true;
// changeFlag == true：数据被更改了，则需要重新遍历
// changeFlag == false：数据没有更改，不需要重新遍历
// 添加数据
public boolean add(String data) {
if (data == null) { // 如果添加的是一个空数据，那增加失败
return false;
}
// 将数据封装为节点，目的：节点有next可以处理关系
Node newNode = new Node(data);
// 链表的关键就在于根节点
if (root == null) { // 如果根节点是空的，那么新添加的节点就是根节点。(第一次调用add方法时，根节点当然是空的了)
root = newNode;
} else {
root.addNode(newNode);
}
this.size++;
return true;
}
// 方法：增加一组数据
public boolean addAll(String data[]) { // 一组数据
for (int x = 0; x < data.length; x++) {
if (!this.add(data[x])) { // 只要有一次添加不成功，那就是添加失败
return false;
}
}
return true;
}
// 方法：删除数据
public boolean remove(String data) { // 要删除的节点，假设每个节点的data都不一样
if (!this.contains(data)) { // 要删除的数据不存在
return false;
}
if (root != null) {
if (root.data.equals(data)) { // 说明根节点就是需要删除的节点
root = root.next; // 让根节点的下一个节点成为根节点，自然就把根节点顶掉了嘛（不像数组那样，要将后面的数据在内存中整体挪一位）
} else { // 否则
root.removeNode(data);
}
}
size--;
return true;
}
// 输出所有节点
public void print() {
if (root != null) {
System.out.print(root.data);
root.printNode();
System.out.println();
}
}
// 方法：获取全部数据
public String[] toArray() {
if (this.size == 0) {
return null; // 没有数据
}
this.foot = 0; // 清零
this.retData = new String[this.size]; // 开辟数组大小
this.root.toArrayNode();
return this.retData;
}
// 获取数据的长度
public int size() {
return this.size;
}
// 判断是否为空链表
public boolean isEmpty() {
return this.size == 0;
}
// 清空链表
public void clear() {
this.root = null;
this.size = 0;
}
// 查询数据是否存在
public boolean contains(String data) { // 查找数据
// 根节点没有数据，查找的也没有数据
if (this.root == null || data == null) {
return false; // 不需要进行查找了
}
return this.root.containsNode(data); // 交给Node类处理
}
// 方法：根据索引取得数据
public String get(int index) {
if (index > this.size) { // 超过个数
return null; // 返回null
}
this.foot = 0; // 操作foot来定义脚标
return this.root.getNode(index);
}
// 定义一个节点内部类（假设要保存的数据类型是字符串）
// 比较好的做法是，将Node定义为内部类，在这里面去完成增删、等功能，然后由LinkList去调用增、删的功能
class Node {
private String data;
private Node next; // next表示：下一个节点对象（单链表中）
public Node(String data) {
this.data = data;
}
// 添加节点
public void addNode(Node newNode) {
// 下面这段用到了递归，需要反复理解
if (this.next == null) { // 递归的出口：如果当前节点之后没有节点，说明我可以在这个节点后面添加新节点
this.next = newNode; // 添加新节点
} else {
this.next.addNode(newNode); // 向下继续判断，直到当前节点之后没有节点为止
}
}
// 判断节点是否存在
public boolean containsNode(String data) { // 查找数据
if (data.equals(this.data)) { // 与当前节点数据吻合
return true;
} else { // 与当前节点数据不吻合
if (this.next != null) { // 还有下一个节点
return this.next.containsNode(data);
} else { // 没有后续节点
return false; // 查找不到
}
}
}
// 删除节点
public void removeNode(String data) {
if (this.next != null) {
if (this.next.data.equals(data)) {
this.next = this.next.next;
} else {
this.next.removeNode(data);
}
}
}
// 输出所有节点
public void printNode() {
if (this.next != null) {
System.out.print("-->" + this.next.data);
this.next.printNode();
}
}
// 获取全部数据
public void toArrayNode() {
LinkList2.this.retData[LinkList2.this.foot++] = this.data;
if (this.next != null) {
this.next.toArrayNode();
}
}
// 根据索引位置获取数据
public String getNode(int index) {
if (LinkList2.this.foot++ == index) { // 当前索引为查找数值
return this.data;
} else {
return this.next.getNode(index);
}
}
}
}
