单链表的特点是只能从头开始向后遍历，所以我们在增删查改的过程中都要考虑从头开始的问题，单链表的临界情况是对于头结点的操作，我们需要对头节点多加考虑。
通过画图来解决单链表的基本操作
-
头部插入
-
中间位置插入
-
删除头结点
-
删除中间结点
-
查找结点
-
修改结点
代码实现这些功能
class NodePractice{
//存储结点的内容
int data;
//存储下一个结点的地址
NodePractice next;
public NodePractice(int data) {
this.data = data;
}
}
public class SingleLinkedListPractice {
//存储链表结点的个数
int size;
//存储头结点的地址
NodePractice head;
/**
* 头插
* @param data
*/
public void addFirst(int data)
{
NodePractice nodePractice=new NodePractice(data);
//如果当前单链表一个元素都没有直接添加
if(size==0)
{
//头结点就是我们要插入的这个元素
head=nodePractice;
size++;
}
else
{
//如果当前链表有元素，就让我们要插入的元素指向原来的头结点
nodePractice.next=head;
//再把头结点变成我们新插入的元素
head=nodePractice;
size++;
}
}
/**
* 中间任意位置插
* @param index
*/
public void addIndex(int index,int data){
//判断索引是否合法
if(index < 0 || index > size)
{
System.out.println("index illegal");
return;
}
//如果在0索引位置插入元素就是头插
if(index==0)
{
addFirst(data);
return;
}
//单链表只能从前向后遍历，所以我们要从头结点一个一个向后遍历直到index的前一个位置
//这里就是待插入元素的前驱结点
NodePractice prev=head;
for (int i = 0; i < index-1; i++) {
prev=prev.next;
}
NodePractice nodePractice=new NodePractice(data);
//带插入元素指向原本前驱结点的下一个元素
nodePractice.next=prev.next;
//再将前驱结点与新插入元素连接
prev.next=nodePractice;
size++;
}
/**
* 尾插
* @param data
*/
public void addLast(int data)
{
//尾插就是index为size的任意位置插入
addIndex(size,data);
}
/**
* 检查索引是否合法，用于删查改
* @param index
* @return
*/
public boolean checkIndex(int index){
//用于删查改的索引范围在0<=index<size
if(index < 0 || index >size-1)
{
System.out.println("index illegal");
return false;
}
return true;
}
/**
* 删除index下标的元素
* @param index
*/
public void removeIndex(int index){
//先判断index下标是否合法
if(checkIndex(index))
{
//如果要删除首元素
if(index==0)
{
NodePractice nodePractice=head;
//head直接指向下一个元素
head=head.next;
//再将原来头元素和第二个元素的链接断开
nodePractice.next=null;
size--;
return;
}
else
{
//如果要删除中间位置的元素依旧要从头开始遍历到前驱结点
NodePractice prev=head;
for (int i = 0; i < index-1; i++) {
prev=prev.next;
}
NodePractice nodePractice=prev.next;
prev.next=nodePractice.next;
nodePractice.next=null;
size--;
}
}
}
/**
* 判断data是否为链表中的元素
* @param data
* @return
*/
public boolean checkData(int data) {
//从头元素开始遍历是否有该元素
NodePractice nodePractice=head;
for (int i = 0; i < size; i++) {
if(nodePractice.data==data)
{
return true;
}
nodePractice=nodePractice.next;
}
return false;
}
/**
* 删除第一个data元素
* @param data
*/
public void removeFirstData(int data)
{
if(checkData(data))
{
//如果首元素就是待删除元素，那么直接利用删除头结点的方法
if(head.data==data)
{
removeIndex(0);
}
NodePractice prev=head;
//如果待删除元素不是头元素，那么我们从头结点的下一个元素开始遍历
while (prev.next != null)
{
if(prev.next.data==data)
{
NodePractice nodePractice=prev.next;
prev.next=nodePractice.next;
nodePractice.next=null;
size--;
return;
}
}
}
}
/**
* 删除所有的data元素
* @param data
*/
public void removeAllData(int data){
//如果链表不为空且第一个元素就是要删除的元素
//但是我们也不确定链表最开始有几个连续的data元素需要删除所以利用while循环一次性删除
while (head != null && head.data==data)
{
NodePractice nodePractice=head;
head=head.next;
nodePractice.next=null;
size--;
}
//链表最开始就为空，或从头结点开始所有元素都是要删除的元素，删除之后链表为空
if(head == null)
{
return;
}
//当链表不为空，且头结点不是待删除元素
//从头结点的下一个节点开始遍历删除
NodePractice prev=head;
while (prev.next != null)
{
//这里可能会有连续的带删除元素，所以不需要没删除一个元素就将前驱结点向后移
//可以等到不是带删除元素的时候再移动
if(prev.next.data==data)
{
NodePractice nodePractice=prev.next;
prev.next=nodePractice.next;
nodePractice.next=null;
size--;
}
else
{
prev=prev.next;
}
}
}
/**
* 查找index下标的元素，并返回该元素
* @param index
* @return
*/
public int seekIndex(int index){
//先判断index索引的合法性
if(checkIndex(index))
{
//从头结点开始遍历
NodePractice nodePractice=head;
for (int i = 0; i < index; i++) {
nodePractice=nodePractice.next;
}
return nodePractice.data;
}
return -1;
}
/**
* 查找data元素并返回索引
* @param data
* @return
*/
private int count;
public int seekData(int data){
//从头节点开始遍历，当找到要查找的元素的时候返回
NodePractice nodePractice=head;
for (int i = 0; i < size; i++) {
if(nodePractice.data==data)
{
System.out.println("找到了");
return count;
}
nodePractice=nodePractice.next;
count++;
}
System.out.println("没找到");
return -1;
}
/**
* 将index下标的元素改成data
* @param index
* @param data
*/
public void setIndex(int index,int data){
//判断索引的合法性
if(checkIndex(index))
{
//从头节点开始遍历找到要修改的下标将元素进行修改
NodePractice nodePractice=head;
for (int i = 0; i < index; i++) {
nodePractice=nodePractice.next;
}
nodePractice.data=data;
}
}
/**
* 将所有的oldData元素改为newData
* @param oleData
* @param newData
*/
public void setData(int oleData, int newData){
if(checkData(oleData))
{
//从头结点开始遍历
NodePractice nodePractice=head;
for (int i = 0; i < size; i++) {
//碰到与原数相同直接修改
if(nodePractice.data==oleData)
{
nodePractice.data=newData;
}
nodePractice=nodePractice.next;
}
}
}
//toString方法的覆写
@Override
public String toString() {
String ret="";
NodePractice nodePractice=head;
for (int i = 0; i < size; i++) {
ret+=nodePractice.data+"->";
nodePractice=nodePractice.next;
}
ret+="NULL";
return ret;
}
public static void main(String[] args) {
SingleLinkedListPractice singleLinkedListPractice=new SingleLinkedListPractice();
singleLinkedListPractice.addFirst(9);
singleLinkedListPractice.addFirst(7);
singleLinkedListPractice.addFirst(5);
singleLinkedListPractice.addFirst(3);
singleLinkedListPractice.addFirst(3);
singleLinkedListPractice.addFirst(3);
singleLinkedListPractice.addFirst(1);
singleLinkedListPractice.addFirst(3);
singleLinkedListPractice.addFirst(3);
singleLinkedListPractice.addFirst(3);
System.out.println(singleLinkedListPractice);
singleLinkedListPractice.setData(3,6);
System.out.println(singleLinkedListPractice);
}
}