正文
算法是什么（二）手写个链表（java）
提示：扫一扫查出行【扫一扫了解最新限行尾号】
复制提示
算法是什么（二）手写个链表（java）
liuyuhang原创，未经允许禁止转载
目录
算法是什么（〇）
很多语言的API中都提供了链表实现，或者扩展库中实现了链表。
但是更多的情况下，Map（或hash）和List（非定容数组）的使用率更高。
这并非意味着链表不应该掌握或不使用了。
链表本质上是一种及其高等的数据结构展现，扩展性极强。
链表可轻松扩展成树结构，二叉树，环，栈，队列，双向队列等。
很多种数据结构都是依据链表的形式扩展出来的，虽然我知道的并不多，但是我知道链表的重要性。
所以，手写一个链表试试。
1、本质
链表的本质是Node（节点），其中保存着信息（info），前一个节点（prevNode），后一个节点（nextNode）。
和基础操作API构成
2、特性
链表为了操作的方便性，多数会将链表做成双向链表，即既包含next，又包含prev
3、基础API
链表的操作，至少需要增删改查，不然还算啥容器了：
增：默认从末尾添加，添加指定index，在首添加三种方式添加单一元素。
删：删除头，删除尾，删除指定index的元素，删除当前指针元素。
改：设置头，设置尾，设置指定index的元素，设置当前指针元素。
查：获取当前指针元素，获取首元素，获取尾元素，获取下一个元素，获取上一个元素，获取指定index的元素
有些API还提供了更多的操作：
获取当前容器的size
获取当前指针的index
迭代器
排序工具
判空
克隆
转数组
逆转
去重复
序列化
等等。。。
链表可做的操作会比想象的多的多。
4、Java中的链表
Java中常用的链表是LinkedList，实现了List接口，继承AbstractLinkedList。同时还有其他接口
同时，还有Queue大类，并非在Collection接口下，但是底层有些是使用链表实现的，功能有些是重复的。
对于需要作为原子操作的各种功能的队列来说，可以考虑。
在扩展Java中的链表的时候，有几种方式供选择：
①继承LinkedList，添加扩展算法；
②实现List，继承AbstractLinkedList，同时扩展算法；
③使用装饰模式，在构造器中调用链表的构造器，同时扩展算法；
④不受约束自己写一个吧。。。
5、写一个简单的链表
我尝试写了一个简单的链表，以前也大概看过C的链表和Java的链表，写的过程中全凭记忆，
大约花了十个小时才写完，哩哩啦啦好多天。
代码拙劣，为了以后尝试链表的其他算法（排序，转换，反转，环链表，扩展二叉树）做准备。
代码如下：
package com.FM.ArrayStudy;
public class SimpleLinkedList<T> {
private Node<T> pointer;// 当前指针节点
private Node<T> firstNode;// 首个节点
private Node<T> lastNode;// 末尾节点
private Integer index = 0;// 当前指针index
private Integer size = 0;// 当前容量
/**
* 获取当前pointer的info
* @return
*/
public T getThis() {
if (null == pointer) {
return firstNode.info;
} else {
return pointer.info;
}
}
/**
* 获取下一个元素的内容,若没有下一个元素,则返回null
*
* @return
*/
public T getNext() {
if (index.equals(size - 1)) {
return null;
} else {
if (null == pointer) {
pointer = firstNode;
pointer = pointer.next;
T info = pointer.info;
index++;
return info;
} else {
pointer = pointer.next;
T info = pointer.info;
index++;
return info;
}
}
}
/**
* 修改指定index的元素的方法
*
* @param index
* @param t
* @throws Exception
*/
public void set(Integer index, T t) throws Exception {
if (index > -1 && index < size - 1) {
Node<T> node = getNodeByIndex(index);
node.info = t;
} else {
throw new Exception("get ele " + index + " out of index");
}
}
/**
* 修改首元素
*
* @param t
*/
public void setFirst(T t) {
firstNode.info = t;
}
/**
* 修改尾元素
*
* @param t
*/
public void setLast(T t) {
lastNode.info = t;
}
/**
* 从指定index移除node的方法
*
* @param index
* @throws Exception
*/
public void remove(Integer index) throws Exception {
if (index > -1 && index < size) {
if (index.equals(0)) {
Node<T> node = getNodeByIndex(1);
firstNode = node;
firstNode.prve = null;
} else if (index.equals(size - 1)) {
Node<T> node = getNodeByIndex(size - 2);
lastNode = node;
lastNode.next = null;
} else {
Node<T> node = getNodeByIndex(index);
Node<T> nextNode = node.next;
Node<T> prveNode = node.prve;
prveNode.next = nextNode;
nextNode.prve = prveNode;
node = null;
}
size--;
} else {
throw new Exception("get ele " + index + " out of index");
}
}
/**
* 获取当前元素在链表中的位置
*
* @return
*/
public int getIndex() {
return index;
}
/**
* 获取当前链表size的方法
*
* @return
*/
public Integer size() {
return size;
}
/**
* 判断容器是否为空的方法,为空返回true
*
* @return
*/
public boolean isEmpty() {
if (size.equals(0)) {
return true;
} else {
return false;
}
}
/**
* 根据index查询链表中元素的方法
*
* @param index
* @return
* @throws Exception
*/
public T getByIndex(Integer index) throws Exception {
if (index > -1 && index < size) {
Node<T> nodeByIndex = getNodeByIndex(index);
return nodeByIndex.info;
} else {
throw new Exception("get ele " + index + " out of index");
}
}
/**
* 根据index获取node的方法
*
* @param index
* @return
*/
private Node<T> getNodeByIndex(Integer index) {
Node<T> temp = firstNode;// 取firstnode
if (index != 0) {// 查看当前index,若index!=0,则递归直到index
for (int i = 0; i < index; i++) {
temp = temp.next;
}
}
this.index = index;// 调整当前index
return temp;// 返回节点
}
/**
* 向链表末尾默认添加一个元素的方法
*
* @param t
*/
public void add(T t) {
if (size == 0) {// 首次创建
Node<T> node = new Node<T>();
firstNode = node;
lastNode = node;
node.info = t;
size++;
} else {
lastNode.next = new Node<T>();
lastNode.next.info = t;
lastNode.next.prve = lastNode;
lastNode = lastNode.next;
size++;
}
}
/**
* 在首添加元素
*
* @param t
*/
public void addFirst(T t) {
if (size == 0) {
add(t);
} else {
Node<T> node = new Node<T>();
node.info = t;
node.next = firstNode;
node.prve = null;
firstNode.next = node;
size++;
}
}
/**
* 在尾部添加元素
*
* @param t
*/
public void addLast(T t) {
add(t);
}
/**
* Node节点 链表内部数据结构和指针
*
* @author Liuyuhang
* @param <T>
*/
private class Node<T> {
T info;// 储存info
Node<T> next;// 下一个节点指针
Node<T> prve;// 上一个节点指针
@Override
public String toString() {// 同时打印next和prev会导致无限引用,堆栈溢出
return "Node [info=" + info + ", next=" + next + "]";
}
}
@Override
public String toString() {// 打印first节点会因为next引出整个链表的所有内容
return "SimpleLinkedList [node=" + firstNode + "]";
}
}
测试可用，自己拿去玩吧。
以上！
