常见数据结构与算法专题篇之单向链表
因为不是CS科班，一个科研狗偏偏要来码代码，以前没有系统学习过数据结构和算法的知识，后期实践中越来越觉得基础的重要，所以近期开始来刷一波儿基础的数据结构和算法的知识。以下内容是我整理总结的，如果有错误，欢迎指出
链表
链表是一种物理储存结构上非连续、非顺序的储存结构。数据元素的逻辑顺序是依靠链表中指针链接次序实现的。链表有一系列节点组成，这些节点在内存中不必相连。这些节点有数据部分Data和链表指针部分Next组成，其中Next指向下一个节点。这样节点的状态改变可以通过改变指针的指向来实现，效率很高。
这里主要以单链表来说明链表实现基本思路
1. 一个简单的链表示例
首先定义Node类作为数据的载体。
Node 类中需要完成的操作就是添加Node 和 输出数据的方法。这里我们先假设数据就是String 数据。我们往Node类添加这两个方法。
class Node {
private String data;
private Node next;
public Node(String data) {
this.data = data;
}
public void setNext(Node next) {
this.next = next;
}
public String getData() {
return data;
}
public Node getNext() {
return next;
}
/**
* 添加下一个节点
* @param newNode
*/
public void addNode(Node newNode){
if(this.next==null){
this.next=newNode;
}else {
this.next.addNode(newNode);
}
}
/**
* 输出节点数据，这里以简单输出数据
*/
public void printNode(){
System.out.println(this.data);
if(this!=null){
this.next.printNode();
}
}
}
我们还需要专门定义一个Link类的对象专门操作Node。Link中我们需要保存一个根节点，根节点作为链表的头。
class Link{
private Node root;
public void add(String data){
Node newNode=new Node(data);//数据必须要封装在节点中，封装之后才可以操作数据。
if(this.root==null){
this.root=newNode;
}else {
this.root.addNode(newNode);
}
}
public void print(){
if(this.root!=null){
this.root.printNode();
}
}
}
以上我们定义了一个Link 类，主要是要把数据封装在Node 中，通过Link 类操作Node ,避免直接操作Node 数据。
这里我们给出这个简单链表类的完整程序（包含main函数中示例数据）。
class Node {
private String data;
private Node next;
public Node(String data) {
this.data = data;
}
public void setNext(Node next) {
this.next = next;
}
public String getData() {
return data;
}
public Node getNext() {
return next;
}
/**
* 添加下一个节点
* @param newNode
*/
public void addNode(Node newNode){
if(this.next==null){
this.next=newNode;
}else {
this.next.addNode(newNode);
}
}
/**
* 输出节点数据，这里以简单输出数据
*/
public void printNode(){
System.out.println(this.data);
if(this.next!=null){
this.next.printNode();
}
}
}
class Link{
private Node root;
public void add(String data){
Node newNode=new Node(data);//数据必须要封装在节点中，封装之后才可以操作数据。
if(this.root==null){
this.root=newNode;
}else {
this.root.addNode(newNode);
}
}
public void print(){
if(this.root!=null){
this.root.printNode();
}
}
}
public class simpleLink {
public static void main(String[] args){
Link all=new Link();
all.add("data1");
all.add("data2");
all.add("data3");
all.print();
}
}
这里为了展示链表的基本操作形式只给出了最简单的一个链表的示例。代码并不具备实用性，数据是直接进行输出的,以上的代码没有真正对Node类进行很好的封装，用户可以直接操作Node类。
2. 进一步完善链表并添加相应方法
我们通过定义内部内类的方式把Node类数据进行封装（这里我们还是以储存String 数据为例）。ps:这里我本来想说这是某种设计模式，但是并没有学过设计模式啥的，等后来把设计模式看了再来完善一下吧。^^大神求放过。
这里我们贴出代码
public class Link {//用户主要关注Link类
private Node root;//保存根节点
private class Node{//定义内部类Node，定义内部内的不仅仅对Node类进行了很好的封装，而且Node 类可以直接访问外部内的数据
private String data;
private Node next;
public Node(String data) {
this.data = data;
}
public void setNext(Node next) {
this.next = next;
}
public Node getNext(){
return this.next;
}
}
}
2.1 Link类添加增加和取出数据的操作
通过Link 类中新增add()方法实现数据的添加
public void add(String data){
Node newNode=new Node(data);
if(this.root==null){//首先判断root节点是否为空，如果root为空就把新建立的节点设为root节点
this.root=newNode;
}else{
this.root.addNode(newNode);//如果root不为空，将添加交给Node类的addNode方法去处理
}
Link类中确定根节点，然后调用Node的addNode() 方法来实现数据添加
public void addNode(Node newNode){
if(this.next==null){
this.next=newNode;//如果root的下一个节点为空，新节点就加到root后
}else {
this.next.addNode(newNode);//如果root的下一个不为空，就判断下一个的下一个，递归
}
}
2.2 取得保存对象的个数
Link 类中定义一个count 的变量，对对象数量进行记录。每次添加数据或者删除数据后相应地改变count的值。这样要知道保存多少对象的花就可以直接取出count的值。
定义size()方法
private int count;//用来保存对象数量
public int size(){
return this.size();//返回对象的数量
}
要注意是，在add()方法中记得添加
this.count++，这样再每次添加数据后count值就相应改变。
2.3 判断是否为空链表
如果我们通过判断count是否为0就可以判断链表是否为空了。
public boolean isEmpty(){
return this.count==0;//如果个数为0 则返回ture，反之false。
}
2.4 清空链表
整个链表中最关键的就是Link 类的root ,如果我们把root 直接指向null, 那么整个链表就是null了。
public void clean(){
this.root=null;
this.count=0;//注意清空链表后count归零
}
2.5 取得链表中制定索引位置的数据
首先在Link中增加foot属性，用来标记链表索引。然后在Link中增加 get(int index) 方法，用来得到制定索引的数据。
private int foot;
public String get(int index){
if(index>this.count){
return null;
}
this.foot=0;
return this.root.getNode(index);//交给Node类中getNode()方法处理。
}
在Node 类中定义getNode()方法，进行查询并修改foot属性的内容，内部类可以很方便访问外部内属性。
public String getNode(int index){
if(index==Link.this.foot++){
return this.data;
}else{
return this.next.getNode(index);
}
}
2.6 判断制定数据是否存在
首先在Link类中定义一个contains()方法，这个方法首先要判断数据是否为null，如果不为null 继续把判断交给Node类处理。
定义contains()方法
public boolean contains(String data){
if(data==null){
return false;
}
return this.root.containsNode(data);
}
在Node类中定义containsNode方法
public boolean containsNode(String data){
if(data.equals(this.data)){//这里用equals()方法，后期便于扩展数据类型
return true;
}
if(this.next==null){
return false;
}else{
return this.next.containsNode(data);
}
}
2.7 删除数据
Link 类中定义remove()方法用于删除节点数据。首先判断要删除的数据是否是根节点，如果是根节点的话就在Link中直接将根节点指向下一个节点。如果删除的不是根节点，则将操作交给Node类去处理。
public void remove(String data){
if(data.equals(this.root.data)){
this.root=this.root.next;//改变根节点指向下一个
}else{
this.root.next.removeNode(this.root,data);
}
this.count--;
}
定义removeNode()方法
public void removeNode(Node prev,String data){
if(data.equals(this.data)){
prev.next=this.next;
}else {
this.next.removeNode(this,data);
}
}
2.8 返回所有数据
返回所有的数据并保存为对象数组的形式，对象数组必须对用户可见，所以在Link中定义。在Link 中定义toArray()方法，将所有数据以对象数组方式返回。
定义对象数组和 toArray()方法。
private String[] retData;
public String[] toArray(){
if(this.count==0){
return null;
}
this.foot=0;//设置数组的索引
this.retData=new String[this.count];
this.root.toArrayNode();
return this.retData;
}
定义toArrayNode()方法，主要是把链表数据取出保存在对象数组中。
public void toArrayNode(){
Link.this.retData[Link.this.foot++]=this.data;
if(this.next!=null){
this.next.toArrayNode();
}
}
完整的程序清单
public class Link{
private class Node {
private String data;
private Node next;
public Node(String data) {
this.data = data;
}
public void addNode(Node node) {
if (this.next == null) {
this.next=node;
} else {
this.next.addNode(node);
}
}
public void printNode() {
System.out.println(this.data);
if (this.next != null) {
this.next.printNode();
}
}
public String getNode(int index){
if(index==Link.this.foot++){
return this.data;
}else{
return this.next.getNode(index);
}
}
public boolean containsNode(String data){
if(data==this.data){
return true;
}else {
if(this.next!=null){
return this.next.containsNode(data);
}else{
return false;
}
}
}
public void removeNode(Node previous,String data){
if(this.data.equals(data)){
previous.next=this.next;
}else {
this.next.removeNode(this,data);
}
}
public void toArrayNode(){
Link.this.retData[Link.this.foot++]=this.data;
if(this.next!=null){
this.next.toArrayNode();
}
}
}
private Node root;
private int count=0;
private int foot;
private String[] retData;
public void add(String data){//向链表中增加数据
Node newNode=new Node(data);
if(data==null) return;
if(this.root==null){
this.root=newNode;
}else{
this.root.addNode(newNode);
}
this.count++;
}
public void print(){
if(this.root!=null){
this.root.printNode();
}
}
public int size(){//链表的大小
return this.count;
}
public boolean isEmpty(){//判断是否为空链表
return this.count==0;
}
public void clean(){//清空链表
this.root=null;
this.count=0;
}
public String get(int index){
if(index>this.count){
return null;
}else{
return this.root.getNode(index);
}
}
public boolean contains(String data){
if(data==null){
return false;
}
return this.root.containsNode(data);
}
public void remove(String data){
if(this.contains(data)){
if(this.root.data==data){
this.root=this.root.next;
}else {
this.root.next.removeNode(this.root,data);
}
}
}
public String[] toArray(){
if(this.count==0){
return null;
}
this.foot=0;
this.retData=new String[this.count];
this.root.toArrayNode();
return this.retData;
}
}
基本链表的方法都写得差不多了,以上链表为了展示链表结构是以String数据为例。实际使用的大多是用户自定义的对象。
3. 进一步完善简单链表
以上链表中是以保存的String 类型的数据为例的，但是实际生活中更多的是保存用户自己定义的简单JavaBean类对象。我们不想每次定义了Bean类时每次都重新根据这个类来写一个链表，这样不符合代码去重复的初衷。在这里我们通过java 中泛型的特性来改写以上的链表，这样当需要保存用户不同的类对象数据时我们只需要指定相应地泛型类型。
在以上的链表中我们查询数据和删除数据依靠的是String 的equals() 方法，这个方法的实际作用是对象比较，用户指定泛型对象时必须要覆写对象的compare()方法，指定比较规则。
定义泛型的Link类并改写链表，由于基本思路大致相同，所以在这里我们直接贴出完整代码。
public class Link<T>{
private class Node {
private T data;
private Node next;
public Node(T data) {
this.data = data;
}
public void addNode(Node node) {
if (this.next == null) {
this.next=node;
} else {
this.next.addNode(node);
}
}
public void printNode() {
System.out.println(this.data);
if (this.next != null) {
this.next.printNode();
}
}
public T getNode(int index){
if(index==Link.this.foot++){
return this.data;
}else{
return this.next.getNode(index);
}
}
public boolean containsNode(T data){
if(data==this.data){
return true;
}else {
if(this.next!=null){
return this.next.containsNode(data);
}else{
return false;
}
}
}
public void removeNode(Node previous,T data){
if(this.data.equals(data)){
previous.next=this.next;
}else {
this.next.removeNode(this,data);
}
}
public void toArrayNode(){
Link.this.retData.add(this.data);
//Link.this.retData[Link.this.foot++]=this.data;
if(this.next!=null){
this.next.toArrayNode();
}
}
}
private Node root;
private int count=0;
private int foot;
private ArrayList<T> retData;//定义一个ArrayList<T>来保存链表全部数据
public void add(T data){//向链表中增加数据
Node newNode=new Node(data);
if(data==null) return;
if(this.root==null){
this.root=newNode;
}else{
this.root.addNode(newNode);
}
this.count++;
}
public void print(){
if(this.root!=null){
this.root.printNode();
}
}
public int size(){//链表的大小
return this.count;
}
public boolean isEmpty(){//判断是否为空链表
return this.count==0;
}
public void clean(){//清空链表
this.root=null;
this.count=0;
}
public T get(int index){
if(index>this.count){
return null;
}else{
return this.root.getNode(index);
}
}
public boolean contains(T data){
if(data==null){
return false;
}
return this.root.containsNode(data);
}
public void remove(T data){
if(this.contains(data)){
if(this.root.data==data){
this.root=this.root.next;
}else {
this.root.next.removeNode(this.root,data);
}
}
}
public ArrayList<T> toArray(){
if(this.count==0){
return null;
}
this.foot=0;
this.retData=new ArrayList<T>(this.count);
this.root.toArrayNode();
return this.retData;
}
}
以上就是我们改写的链表代码。值得注意的是前面String数据我们通过把链表数据赋给对象数组retData[]来取出数据。在定义了泛型后，没办法进行 T[] retData=new T[this.count]这样类似的初始化一个对象数组。后来在网上看到有人通过T[] retData=(T[])new object[this.count]来进行初始化，但是这种方法可能隐含着ClassCastException的报错。
链表还有很多其他的实现方式，常见的有循环单链表、双向链表、循环双链表。循环单链表实际上就是上面我们链表的最后一个节点指向第一个节点，整体构成一个链环。双向链表主要是链表中包含两个指针，一个指向前驱元，一个指向后继元(LinkList就是双向链表)，循环双向链表就是最后一个节点指向第一个节点。
文中的一部分内容是参考了网易云课堂李兴华老师的java课程。这个课程很适合想要入门Java的初学者，内容很全面。
