链表的递归实现
在课程github里没找到链表的递归实现代码，所以自己实现了一遍。希望后面同学自己实现的时候可以参考。
如果代码有问题，欢迎评论指正。
package com.imooc.linkedlist;
public class LinkedListWithRecursion<E> {
private class Node<E> {
public E data;
public Node next;
public Node(E data, Node next) {
this.data = data;
this.next = next;
}
public Node(E data) {
this(data, null);
}
public Node() {
this(null, null);
}
@Override
public String toString() {
return data.toString();
}
}
private Node dummyHead;
private int size;
public LinkedListWithRecursion() {
dummyHead = new Node(null, null);
size = 0;
}
/**
* @return
*/
public int getSize() {
return size;
}
/**
* @return
*/
public boolean isEmpty() {
return size == 0;
}
/**
* 向索引指定位置添加元素
*
* @param e
* @param index
*/
public void add(E e, int index) {
if (index < 0 || index > size) {
throw new IllegalArgumentException("LinkedList.add failed, index is illegal!");
}
Node<E> previous = dummyHead;
addWithRecursiton(e, previous, 0, index);
size++;
}
/**
*
* @param e 待添加的元素
* @param previous 指定插入索引的前一节点
* @param current 当前递归索引
* @param index 指定添加索引
*/
private void addWithRecursiton(E e, Node<E> previous, int current, int index){
if (current == index){
previous.next = new Node(e, previous.next);
return;
}
addWithRecursiton(e, previous.next, current + 1, index);
}
/**
* @param e
*/
public void addFirst(E e) {
add(e, 0);
}
/**
* @param e
*/
public void addLast(E e) {
add(e, size);
}
/**
* 查询索引指定位置的元素
* @param index
* @return
*/
public E get(int index){
if (index < 0 || index >= size) {
throw new IllegalArgumentException("LinkedList.get failed, index is illegal!");
}
Node<E> current = dummyHead.next;
return getWithRecursion(current, 0, index);
}
/**
*
* @param node 当前节点
* @param current 当前递归索引
* @param index 指定索引
* @return
*/
private E getWithRecursion(Node<E> node, int current, int index){
if (current != index){
return (E)getWithRecursion(node.next, current + 1, index);
}
return node.data;
}
/**
*
* @return
*/
public E getFirst(){
return get(0);
}
/**
*
* @return
*/
public E getLast(){
return get(size - 1);
}
/**
* 更新索引指定位置元素
* @param e 新元素
* @param index 待更新元素索引
*/
public void set(E e, int index){
if (index < 0 || index >= size) {
throw new IllegalArgumentException("LinkedList.set failed, index is illegal!");
}
Node current = dummyHead.next;
setWithRecursion(current, e, 0, index);
}
/**
*
* @param node 当前节点
* @param e 带更新元素
* @param current 当前递归索引
* @param index 指定索引
*/
private void setWithRecursion(Node<E> node, E e, int current, int index){
if (current == index){
node.data = e;
return;
}
setWithRecursion(node.next, e, current + 1, index);
}
/**
* 删除索引指定位置元素
* @param index
* @return
*/
public E remove(int index){
if (index < 0 || index >= size) {
throw new IllegalArgumentException("LinkedList.remove failed, index is illegal!");
}
Node previous = dummyHead;
E res = (E)removeWithRecursion(previous, 0, index);
size--;
return res;
}
/**
*
* @param previous
* @param current
* @param index
* @return
*/
private E removeWithRecursion(Node<E> previous, int current, int index){
if (current != index){
return (E)removeWithRecursion(previous.next, current + 1, index);
}
Node<E> delNode = previous.next;
previous.next = previous.next.next;
delNode.next = null;
return (E)previous.next.data;
}
/**
*
* @return
*/
public E removeFirst(){
return remove(0);
}
/**
*
* @return
*/
public E removeLast(){
return remove(size -1);
}
/**
* 查找是否存在元素e
* @param e
* @return
*/
public boolean contains(E e){
Node current = dummyHead.next;
return containsWithRecursion(current, e);
}
/**
*
* @param node
* @param e
* @return
*/
private boolean containsWithRecursion(Node<E> node, E e){
if (node == null){
return false;
}
return node.data == e ? true : containsWithRecursion(node.next, e);
}
@Override
public String toString(){
StringBuilder res = new StringBuilder();
Node current = dummyHead.next;
return toStringWithRecursion(current, res);
}
/**
*
* @param node
* @param res
* @return
*/
private String toStringWithRecursion(Node<E> node, StringBuilder res){
if (node == null){
return res.append("NULL").toString();
}
res.append(node.data + "->");
return toStringWithRecursion(node.next, res);
}
public static void main(String[] args) {
LinkedListWithRecursion linkedList = new LinkedListWithRecursion();
for(int i = 0; i < 5; i ++){
linkedList.addFirst(i);
System.out.println(linkedList);
}
linkedList.add(66, 3);
System.out.println(linkedList);
System.out.println(linkedList.get(3));
linkedList.set(77, 3);
System.out.println(linkedList);
System.out.println(linkedList.remove(3));
System.out.println(linkedList);
System.out.println(linkedList.contains(2));
}
}702
收起
正在回答 回答被采纳积分+3
3回答
相似问题
Hierholer算法的递归实现
645
1
3
利用链表的递归性质求解“链表翻转”问题
789
0
6
请问递归实现一定能转为非递归实现吗？
513
0
3
链表的递归实现add方法NullPointException
676
0
2
登录后可查看更多问答，登录/注册
