单向链表的实现重点在
1. 定义节点,数据变量及指向下一个指针的变量
2. 定义链表类 头结点变量,初始化时默认为null
3. 搜索下标值,循环遍历下标个节点,获取节点的值
4. 插入头结点, 创建新节点,将新节点的下一个节点指向头结点,头结点指向新节点
5. 插入尾结点,循环遍历到最后一个节点,最后一个节点的下一个节点执行新节点
6. 插入指定下标节点, 循环遍历下标-1个节点,创建新节点,将新节点的下一个节点指向目标位置的前一个节点的下一个节点,将目标位置的前一个节点的下一个节点指向新节点
7. 删除执行下标节点, 循环遍历下标-1个节点,将下标-1个节点的下一个节点执行目标位置前一个节点的下一个节点的下一个节点
public class MyLinkedList {/*** 定义列表节点, 包括节点的数据及指向下一个节点的指针*/class Node{int val;Node next;public Node(int val){this.val = val;}}/*** 定义头结点*/Node head;/*** 初始化头结点*/public MyLinkedList() {this.head = null;}/*** 获取指定下标值* @param index* @return*/public int get(int index) {// 如果下标不合法,则直接返回-1if(index<0){return -1;}// 定义临时节点存储头结点Node p = head;// 循环遍历 下标 个 节点for(int i=0;i<index && p!=null;i++){p = p.next;}// 如果已经越界则返回-1if(p==null){return -1;}// 如果有对应下标的节点,则返回对应值return p.val;}/*** 在头结点插入节点* @param val*/public void addAtHead(int val) {// 创建新节点Node node = new Node(val);// 将新节点的下一个节点指向头结点node.next = head;// 头结点指向新节点head = node;}/*** 在尾部插入节点* @param val*/public void addAtTail(int val) {// 如果头结点为空,则直接赋值头结点if(head==null){head = new Node(val);return;}// 创建临时节点指向头结点Node p =head;// 循环下一个节点直至下一个节点为空while(p.next!=null){p = p.next;}// 下一个节点指向新节点p.next = new Node(val);}/*** 指定下标插入节点* @param index* @param val*/public void addAtIndex(int index, int val) {// 如果下标小于等于0,则插入头部if(index<=0){addAtHead(val);return;}// 定义长度变量int len=0;// 定义临时节点执行头结点Node p = head;// 遍历所有节点至最后获取长度while(p!=null){p = p.next;len++;}// 如果下标等于链表长度,则插入链尾if(len == index){addAtTail(val);return;}// 如果下标超过链表长度,则不处理if(index > len){return;}//定义临时节点指向头结点p = head;// 循环遍历下标个-1个节点,获取目标位置的前节点for(int i=0;i<index-1;i++){p = p.next;}// 定义新节点Node node = new Node(val);// 将新节点的下一个节点执行目标位置前一个节点的下一个节点node.next = p.next;// 将目标节点的前一个节点指向新节点p.next = node;}/*** 删除执行下标节点* @param index*/public void deleteAtIndex(int index) {// 定义长度变量int len = 0;// 定义临时节点变量指向头节点Node p = head;// 循环遍历获取长度while (p!=null){len++;p = p.next;}// 如果删除下标合法范围内, 则给予处理if(index>=0 &&index<len){// 如果删除为头部,则直接将头结点指向下一个节点if(index == 0){head = head.next;return;}// 定义临时节点变量指向头结点p=head;// 循环遍历 下标-1个节点for(int i=0;i<index-1;i++){p = p.next;}// 将删除目标位置的前一个节点的下一个节点指向// 前一个节点的下一个节点的下一个节点p.next = p.next.next;}}}