Github issues:https://github.com/littlejoyo/Blog/issues/
微信公众号：Joyo说
链表是基本的数据结构，笔试或者面试的时候也是常常考察的内容，所以实现一个简单的单链表以及对链表的基本操作要学会信手拈来，面试的时候才能临危不惧吧，加油。
单链表的结构
单链表结构
上面展示的是一个单链表的存储原理图，简单易懂，head为头节点，他不存放任何的数据，只是充当一个指向链表中真正存放数据的第一个节点的作用，而每个节点中都有一个next引用，指向下一个节点，就这样一节一节往下面记录，直到最后一个节点，其中的next指向null。
代码实现单链表
链表节点的定义
链表是由一个个节点连接形成的，所以要先定义好节点类，节点类主要分为两块内容就是数据和next指针，定义可以参看下面代码：
public class LinkListDemo {
//节点类
private class ListNode {
private Object data;
private ListNode next = null;
ListNode() {
data = null;
}
ListNode(Object data) {
this.data = data;
}
}
private ListNode head;//头节点
private ListNode temp;//临时节点
//初始化链表，生成一个无数据的头节点
LinkListDemo() {
head = new ListNode();
}
}
给链表添加节点
/* ================以下方法是对链表的操作===================*/
/**
* 增加节点
*
* @param data
*/
public void addNode(Object data) {
ListNode node = new ListNode(data);
temp = head;
while (temp.next != null) {
temp = temp.next;
}
temp.next = node;
}
对于插入节点常用的思想主要有头插法 和 尾插法，使用尾插法的话需要再定义一个尾指针来区分。下面可以通过对比讨论他们的不同：
头插法和尾插法的对比
返回链表的长度
/**
* 返回链表的长度
* @return
*/
public int getLength()
{
temp = head;
int length = 0;
while (temp.next!=null)
{
length++;
temp = temp.next;
}
return length;
}
增加节点到链表指定的位置
对于传入的index需要先判断是否合法，然后通过while循环的遍历寻找index的位置来进行节点的插入。
/**
* 增加节点到指定的位置
*
* @param index
* @param data
*/
public void addNodeByIndex(int index, Object data) {
if (index < 1 || index > getLength() + 1) {
System.out.println("插入的位置不合法。");
return;
}
int count = 1; //记录遍历的位置
ListNode node = new ListNode(data);
temp = head;
while (temp.next != null) {
if (index == count++) {
node.next = temp.next;
temp.next = node;
return;
}
temp = temp.next;
}
}
删除链表指定位置的节点
实现的思路和上面的相似，只是增删节点的处理过程不相同。
/**
* 删除指定位置的节点
*
* @param index
*/
public void deleteByIndex(int index) {
if (index < 1 || index > getLength()) {
System.out.println("插入的位置不合法。");
return;
}
int count = 1;//记录位置
temp = head;
while (temp.next != null) {
if (index == count++) {
temp.next = temp.next.next;
return;
}
temp = temp.next;
}
}
从头到尾打印链表的数据
/**
* 从头到尾打印节点
*/
public void printListFromHead() {
temp = head;
while (temp.next != null) {
System.out.print("{" + temp.next.data + "}");
temp = temp.next;
}
System.out.println();
}
从尾到头打印链表的数据
这里可以利用栈的后进先出的存储特点来实现。
/**
* 从头到尾打印节点
*/
public void printListFromHead() {
temp = head;
while (temp.next != null) {
System.out.print("{" + temp.next.data + "}");
temp = temp.next;
}
System.out.println();
}
测试链表是否能成功建立以及各个方法能否实现
public static void main(String[] args)
{
LinkListDemo list = new LinkListDemo();
list.addNode(1);
list.addNode(2);
list.addNode(3);
list.addNode(4);
list.addNode(5);
list.printListFromHead();
list.addNodeByIndex(3,2.8);
list.printListFromHead();
list.deleteByIndex(3);
list.printListFromHead();
list.printFromTail();
System.out.println(list.getLength());
}
输出结果：
{1}{2}{3}{4}{5}
{1}{2}{2.8}{3}{4}{5}
{1}{2}{3}{4}{5}
{5}{4}{3}{2}{1}
5
微信公众号
扫一扫关注Joyo说公众号，共同学习和研究开发技术。
关注我
