Java 实现单链表以及单链表的反转
package test;
import java.util.Iterator;
public class LinkList<T> implements Iterable<T>{
// 头节点
private Node head;
// 记录链表长度
private int N;
public LinkList(){
// 初始化头节点
head = new Node(null, null);
N = 0;
}
// 清空链表
public void clear(){
head.item = null;
head.next = null;
N = 0;
}
// 获取链表长度
public int length(){
return N;
}
// 判断链表是否为空
public boolean isEmpty(){
return N==0;
}
// 获取指定位置i处的值
public T get(int i){
if(i<0 || i>=N){
throw new RuntimeException("位置不合法!");
}
Node n = head.next;
for(int index = 0; index < i; index++){
n = n.next;
}
return n.item;
}
// 向链表中插入元素t
public void insert(T t){
Node n = head;
// 找到最后一个节点
while(n.next != null){
n = n.next;
}
Node newNode = new Node(t,null);
n.next = newNode;
N++;
}
// 向指定位置i处插入元素t
public void insert(int i, T t){
if(i < 0 || i >= N){
throw new RuntimeException("位置不合法!");
}
// 找到位置i的前一个节点
Node pre = head;
for(int index = 0; index <= i-1; index++){
pre = pre.next;
}
// 位置i上的节点
Node curr = pre.next;
// 让待插入节点的下一个节点指向当前i所在的节点
Node newNode = new Node(t, curr);
// 让位置i的前一个节点的下一个节点指向新节点
pre.next = newNode;
// 链表长度加一
N++;
}
// 删除指定位置i处的节点,并返回被删除元素
public T remove(int i){
if(i < 0 || i >= N){
throw new RuntimeException("位置不合法!");
}
// 找到位置i的前一个节点
Node pre = head;
for(int index = 0; index <= i-1; index++){
pre = pre.next;
}
// 位置i处节点
Node curr = pre.next;
// 让i处节点的前一个节点的下一个节点指向i处节点的下一个节点
pre.next = curr.next;
// 长度减一
N--;
return curr.item;
}
// 查找元素t在链表中第一次出现的位置
public int indexOf(T t){
// 遍历整个链表
Node n = head.next;
for(int index = 0; index < N; index++){
// 找到相等的值就退出循环
if(n.item.equals(t)){
return index;
}
n = n.next;
}
return -1;
}
/**
* 节点类
* @author Administrator
*
*/
private class Node{
// 节点数据
T item;
// 下一个节点
Node next;
public Node(T item, Node next){
this.item = item;
this.next = next;
}
}
@Override
public Iterator<T> iterator() {
return new MyIterator();
}
private class MyIterator implements Iterator<T>{
private Node n;
public MyIterator(){
this.n = head;
}
@Override
public boolean hasNext() {
return n.next != null;
}
@Override
public T next() {
n = n.next;
return n.item;
}
}
public void reverse(){
if(N == 0){
return;
}
reverse(head.next);
}
/**
* 使用递归完成反转,从原链表的第一个节点开始,依次递归调用反转每一个节点,
* 直到把最后一个节点反转完毕,整个链表就反转完毕。
* @param curr 当前遍历的节点
* @return 反转后当前节点的上一个节点
*/
public Node reverse(Node curr){
// 已经到了最后一个节点
if(curr.next == null){
// 头节点的下一个节点指向原链表的最后一个节点
head.next = curr;
return curr;
}
// 递归调用,对下一个节点进行反转
Node pre = reverse(curr.next);
pre.next = curr;
curr.next = null;
return curr;
}
}
测试类:
package test;
public class TestClass {
public static void main(String[] args) {
LinkList<String> list = new LinkList<>();
list.insert("张三");
list.insert("李四");
list.insert("王五");
list.insert("赵六");
System.out.println("length:" + list.length());
System.out.println("赵六所在位置:" + list.indexOf("赵六"));
System.out.println("_______________");
// 测试插入
list.insert(2, "xiaoli");
for(String s : list){
System.out.println(s);
}
// 测试删除
list.remove(3);
System.out.println("_______________");
for(String s : list){
System.out.println(s);
}
System.out.println("_______________");
// 测试链表反转
list.reverse();
for(String s : list){
System.out.println(s);
}
}
}
结果: