简介
如上图所所示，每个节点包含两个成员变量：data和next(这里只是举一个最简单的例子，实际上有多少个成员变量，视需求而定)，data可以是任意类型的，视需求而定；next就是node类型(node到底是什么类型，也是视需求而定)，每一个节点的next指向他的下线节点，所以拿到一个节点后，可以直接拿到他的下线节点，如果下线节点不为空的话，一般把链表的第一个节点称为头节点，头节点没有上线节点，对于一个链表，拿到了他的头节点就相当于拿到了这个链表；最后一个节点称为尾节点，尾没有下线节点，其他的节点都会有下线节点，如果发现某个节点的next为空，即node.next = null，说明这个节点就是尾节点，这在遍历链表的时候经常用到；需要注意的是，在内存中，各个节点的内存地址不是连续的，而是离散的。
优缺点
创建单链表
添加头节点
实现思路：如果链表没有头结点，新结点直接成为头结点；否则新结点的next直接指向当前头结点，并让新结点成为新的头结点。
添加尾结点
实现思路：如果链表没有头结点，新结点直接成为头结点；否则需要先找到链表当前的尾结点，并将新结点插入到链表尾部。
指定位置添加节点
实现思路：先判断插入位置为头尾两端的情况，即index == 0插入到头部，index == size()插入到尾部；如果插入位置不是头尾两端，则先找出当前index位置的结点cur以及前一个结点 pre，然后cur成为新结点的下一个结点，新结点成为pre的后一个结点，这样就成功插入到index位置。
删除指定位置节点
实现思路：找出当前index位置的结点cur以及前一个结点 pre，pre.next直接指向cur.next即可删除cur结点。
增加头节点
链表的反转
实现思路：在链表遍历的过程中将指针顺序置换，即每遍历一次链表就让cur.next指向pre，最后一个结点成为新的头结点。反转之后指针入下图红线所示。
代码
public class SingleList {
//头节点
private Node head;
private int size;
class Node{
private T value;
private Node next;
//创建节点时赋值,当前节点的下一个指针为null
public Node(T value) {
this.value = value;
this.next =null;
}
@Override
public String toString() {
return "Node{" +
"value=" +value +
", next=" +next +
'}';
}
}
/**
* 添加头节点
* 1、头节点不存在，直接赋值
* 2、头节点存在，将新的节点变为头节点的，原来的头节点指向现在的头节点
*/
public void addHeadNode(T value){
//创建节点
Node newNode =new Node(value);
//如果头节点不存在，设置当前节点为头节点。
if(head==null){
head =newNode;
return;
}
//新节点next直接指向当前头头节点。
//新节点变为头节点
newNode.next =head;
head =newNode;
}
/**添加节点到尾部
* @param value
*/
public void addTailNode(T value){
//创建节点
Node node =new Node(value);
//如果节点是否存在,不存在直接放到头部
if(null==head){
head =node;
return;
}
//找到最后一个节点
Node last =head;
while(last.next!=null){
last = last.next;
}
//将新节点放入最后一个节点的next
last.next =node;
}
/**添加到指定位置
* @param value 值
* @param index 集合位置
*/
public void addNodeAtIndex(T value,int index){
//校验存放的位置
if(index<0|| index>size()){
throw new IndexOutOfBoundsException("IndexOutOfBoundsException");
}
//
if(index==0){
addHeadNode(value);
}else if(index==size()) {
//放入尾部
addTailNode(value);
}else {
//插入中间位置
Node node =new Node(value);
int position =0;
Node cur =head;//标记当前节点
Node pre =null;//记录当前位置节点
while(cur!=null){
if(position==index){
node.next=cur;
pre.next=node;
return;
}
pre = cur;
cur = cur.next;
position++;
}
}
}
public void deleteNodeAtIndex(int index){
//校验范围
if(index<0||index>size()-1){
throw new IndexOutOfBoundsException("IndexOutOfBoundsException");
}
//删除头节点
if (index ==0) {
head =head.next;
return;
}
//遍历结点
Node cur =head;
Node pre =null;
int position =0;
while (cur!=null){
if(index==position){
pre.next = cur.next;
//断开与节点的链接,jvm会回收
cur.next =null;
return;
}
pre = cur;
cur = cur.next;
position++;
}
}
public void reverse(){
Node cur =head;//当前节点
Node pre =null;//标记当前节点的上一个节点。
Node temp;
while (cur !=null){
//保存当前节点的下一个节点,将上一个节点和当前节点置换
temp = cur.next;
cur.next=pre;
//pre、cur 继续后移
pre = cur;
cur = temp;
}
head = pre;
}
public int size(){
int size =0;
if(head==null){
return size;
}
Node cur =head;
while(cur!=null){
cur = cur.next;
size++;
}
return size;
}
@Override
public String
toString() {
return "SingleTest{" +
"head=" +head +
'}';
}
}
