JAVA数据结构之链表
什么是链表呢？
链表作为最基本的数据结构之一，定义如下：
链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。
简单来说呢，链表就是由一系列节点组成的，每个节点都包括两个部分，一个是该节点的值，另一个就是对于下一个节点的引用。
链表的结构表示图
链表的实现
public class ListNode {
//链表节点存放的数据
int val;
//链表的无参构造方法
public ListNode(){
}
//指向下一个节点的引用
ListNode next;
//链表的有参构造方法
public ListNode(int val){
this.val=val;
}
}
链表常用的操作
末尾插入节点：
/**
* 链表末尾插入节点
* @param node
*/
public void insertListNodeLast(ListNode node){
if(head==null){
head=new ListNode();
}
ListNode temp=head;
while(temp.next!=null){
temp=temp.next;
}
temp.next=node;
}
注意的是需要使用一个临时指针temp用来指向链表的最后节点，其中while(temp.next!=null)代表当前是最后一个节点，而while(temp!=null)代表已经遍历完链表了，当前为空。
头部插入节点：
/**
* 头部插入节点
* @param node
*/
public void insertListNodeHead(ListNode node){
if(head==null){
head=new ListNode();
}
node.next=head.next;
head.next=node;
}
获取链表的长度：
/**
* 获取链表的长度
* @return
*/
public int getLength(){
if(head==null){
head=new ListNode();
}
ListNode temp=head;
int count=0;
while(temp.next!=null){
count++;
temp=temp.next;
}
return count;
}
将节点插入指定位置：
/**
* 将节点插入指定位置
* @param position
* @param node
*/
public void insertListNode(int position,ListNode node){
if(head==null){
head=new ListNode();
}
ListNode temp=head;
int count=0;
while(temp.next!=null){
if(position==count){
node.next=temp.next;
temp.next=node;
return;
}
count++;
}
temp.next=node;
}
删除指定位置的元素：
/**
* 删除链表中指定节点
* @param position
*/
public void delete(int position){
if(head==null){
head=new ListNode();
}
if(position<1){
return;
}
ListNode temp1=head.next;
ListNode temp2=head;
int count=0;
for(int i=1;i<position;i++){
temp1=temp1.next;
temp2=temp2.next;
}
temp2.next=temp1.next;
}
这里删除节点采用的是双指针的方法，temp2指向删除节点，temp1指向删除节点的下一个节点，当遍历到删除节点的时候，只需要将temp1指向的节点赋给temp2.next就可以了。特殊情况是删除末尾节点，此时temp2指向末尾节点，而temp1此时为末尾节点，指向为空，temp2.next=temp1.next相当于直接将temp2指向为空。
遍历整个链表：
public void listPrint(ListNode node){
ListNode temp= head.next;
while(temp!=null){
System.out.println("data: "+temp.val);
temp=temp.next;
}
}
以上就是对单链表的基本操作了。