说明
单链表里面的数据元素是以结点为单位，每个结点是由数据元素的数据和下一个结点的地址组成
在java集合框架里面 LinkedList、HashMap（数组加链表）等等的底层都是用链表实现的。
链表结果
添加元素
删除
特点
数据元素在内存中存放的 地址是不连续的：单链表的结点里面还定义一个结点，它里面保存着下一个结点的内存地址，在实例化对象的时候，jvm会开辟不同内存空间，并且是不连续的。
添加效率高：添加一个元素时，先找到插入位置的前一个，只需要将1，2个元素的连接断开，将插入结点的next指向第一个元素的next
java
节点类
/**
* 节点类
* @author mym
*
*/
public class Node {
private Object data;
private Node next;
public Node(Object data) {
this.data = data;
}
public Object getData() {
return data;
}
public void setData(Object data) {
this.data = data;
}
public Node getNext() {
return next;
}
public void setNext(Node next) {
this.next = next;
}
}
链表类
public class MyLinked {
/**
* 第一个节点
*/
private Node head;
/**
* 链表长度，即：节点数量
*/
private int size = 0;
/**
* 在尾部添加节点
* @param data
*/
public void add(Object data){
add(size,data);
}
/**
* 插入节点
* @param index
* @param data
*/
public void add(int index,Object data){
// 索引校验
if(index < 0){
throw new IndexOutOfBoundsException("index 不能小于 0");
}
// index 可以等于 size（长度），表示插入到末尾，但不能大于size（长度）
if(index > size){
throw new IndexOutOfBoundsException("index 不能大于长度，长度是： "+size);
}
Node node = new Node(data);
if(index == 0){ // 头部插入节点
if( head == null){ // 如果链表是空，没有元素
head = node;
}else{ // 如果链表不为空，有元素
node.setNext(head);
head = node;
}
}else{ // 中间添加节点、或 尾部添加节点
Node temp = head;
// 循环取出添加节点的前一个位置
for(int i = 1; i<index;i++){
temp = temp.getNext();
}
Node oldNext = temp.getNext();
// 让前一个节点指向新节点
temp.setNext(node);
// 新节点指向原来的下一个节点
node.setNext(oldNext);
}
size ++;
}
/**
* 根据索引取出节点
* @param index
* @return
*/
public Object get(int index){
// 索引校验
if(index < 0){
throw new IndexOutOfBoundsException("index 不能小于 0");
}
if(size == 0){
throw new IndexOutOfBoundsException("长度是： "+size+"，没有元素");
}
if(index >= size){
throw new IndexOutOfBoundsException("index 不能大于等于长度，长度是： "+size);
}
Node ret = null;
if(index == 0){ // 取出第一个节点
ret = head;
}else{ // 取出中间阶段
Node temp = head;
// 循环指定的索引位置，取出该节点
for(int i = 0; i<index;i++){
temp = temp.getNext();
}
ret = temp;
}
return ret.getData();
}
/**
* 删除指定索引的节点
* @param i
* @return
*/
public Object remove(int index){
// 索引校验
if(index < 0){
throw new IndexOutOfBoundsException("index 不能小于 0");
}
if(size == 0){
throw new IndexOutOfBoundsException("长度是： "+size+"，没有元素");
}
if(index >= size){
throw new IndexOutOfBoundsException("index 不能大于等于长度，长度是： "+size);
}
Node ret = null;
if(index == 0){ // 删除第一个节点
ret = head;
// 将第一个节点的下一个节点作为第一个节点
head = head.getNext();
}else{ // 取出中间阶段
Node temp = head;
// 循环，取出要删除节点的前一个节点
for(int i = 0; i<index-1;i++){
temp = temp.getNext();
}
//取出要删除的节点
ret = temp.getNext();
// 取出要删除节点的下一个节点
Node next = ret.getNext();
// 让前一个节点，指向下一个节点
temp.setNext(next);
}
size--;
return ret.getData();
}
public int size(){
return size;
}
}
测试类
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
public class TestLinked {
public static void main(String[] args) {
MyLinked link = new MyLinked();
link.add(0,"李雷");
link.add("韩梅梅");
link.add(0,"lucy");
link.add(2,"lili");
link.add(link.size(),"张三");
// Object obj2 = link.remove(0);
// System.out.println("删除："+obj2);
//
// Object obj3 = link.remove(link.size()-1);
// System.out.println("删除："+obj3);
Object obj3 = link.remove(2);
System.out.println("删除："+obj3);
System.out.println("----");
// 遍历
for(int i = 0;i<link.size();i++){
Object obj = link.get(i);
System.out.println(obj);
}
}
public static void main2(String[] args) {
// 测试校验
MyLinked l = new MyLinked();
l.add("李雷");
// l.add(-10, "");
// l.add(10, "");
// l.get(-10);
// l.get(10);
// l.get(0);
// l.remove(-10);
l.remove(10);
}
public static void main1(String[] args) {
List list = new ArrayList();
// list.add("李雷");
// list.add(-1,"");
// list.add(5, "韩梅梅"); //java.lang.IndexOutOfBoundsException
// list.get(2);
list.get(0);
LinkedList ll = new LinkedList();
}
}