简单java链表
the first passaage
链表的基本构成
代码展示
链表的优缺点分析

the first passaage
在数据结构课上曾用c++实现了链表。 这篇博客我将用java实现简单链表
链表的基本构成

数据：存储节点的属性信息
地址：指向下一个节点的地址

代码展示
// An highlighted block
var foo = 'bar';
class 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;
	}
	public void setData(String data) {
		this.data = data;
	}
	public  String getData() {
		return this.data;
	}
}

public class xue2
{
	public static void main(String args[]) {
		Node root = new Node("火车头");
		Node n1 = new Node("车厢1");
		Node n2 = new Node("车厢2");
		Node n3 = new Node("车厢3");
		root.setNext(n1);
		n1.setNext(n2);
		n2.setNext(n3);
		Node currentNode = root;
		while(currentNode != null) {
			System.out.println(currentNode.getData());
			currentNode = currentNode.getNext();
		}
	}
}
result:
火车头
车厢1
车厢2
车厢3
链表的优缺点分析

结点可以在内存中存在任何地方，不要求连续。
每一个结点都既保存了本节点的数据，也保存了下一个结点的内存地址，通过这个地址找到下一个结点。 就好像只要知道第一个人的座位，通过第一个人就可以知道第二个人的座位号，第二个人知道第三个人的座位号……
增加数据和删除数据很容易。
查找数据时效率低，因为不具有随机访问性，所以访问某个位置的数据都要从第一个数据开始访问，
不指定大小，扩展方便。链表大小不用定义，数据随意增删。

链表的基本结构

public class LNode {
    public String data;//节点数据
    LNode next;//下一个节点
}

这是最基本的链表结构，还有双向链表和循环链表会在文章最后提到。

建立单链表

头部插入建立单链表

头部插入建立方式的思想是,首先建立一个指针， 

1.然后新建第一个节点，让指针指向这个节点 

2.然后再新建一个节点，通过指针拿到第一个点的地址，让新建的下一个地址指向第一个节点。 

3.最后把指针移动到第一个节点上。 

后面重复这个过程就可以

                       

大家可以根据这张图来理解一下。

下面是实现的代码

// 在头部插入
    public LNode Creat_LinkListHead() {
        LNode head = null;// 头部，空表
        System.out.println("现在使用头部插入法，请输入数据，以0为结束");
        String newDate;
        while (!(newDate = in.next()).equals("0")) {
            LNode newNode = new LNode();//新建一个节点
            newNode.data = newDate;
            newNode.next = head;//通过指针找到上一个节点地址，让新节点的下一个地址指向新节点
            head = newNode;//让指针移动到新建的节点上
        }
        System.out.println("录入完毕");
        return head;
    }

在尾部插入建立链表

在头部插入的方式，有一个很大的问题，就是最后我指针的位置，在整个链表逻辑上 的最后位，遍历的时候，会反过来，比方说建立的顺序是ABCDE，遍历的时候就是EDCBA了 

在尾部插入建立的方式就是为解决这个问题 

尾部插入的思路是：首先我们建立一个头节点和一个尾节点，让头节点和尾节点一起指向第一个节点，之后的话头结点不再变动，尾节点用头部插入的方式建立起链表，可以发现这个方式和头部插入没有什么区别，主要就是增加了一个头节点。 
下面是实现的代码

// 在尾部插入
    public LNode Creat_LinkListTail() {
        LNode H = null;// 头指针
        LNode R = null;// 尾指针
        String newDate;
        System.out.println("现在使用尾部插入法，以0为结束");
        while (!(newDate = in.next()).equals("0")) {
            LNode newNode = new LNode();
            newNode.data = newDate;
            // 第一个指针
            if (H == null) {
                H = newNode;
            } else {
                R.next = newNode;
            }
            //指针移动到创建的新节点
            R = newNode;
        }
        //让随后一个节点指向null
        if (R != null)
            R.next = null;
        return H;
    }

带头节点的尾部插入

上面方式也有一个问题，第一个节点由于没有前驱，所以我们在很多操作的时候都要考虑这个特殊的点，这样在增加删除的时候都会比较麻烦，比较好的解决方式，我们可以第一个节点前面在加一个节点，这个节点没有数据，只是指向原来的第一个节点。如下图

                   

H代表的是头指针 

R代表的是尾指针

新增一个头结点后就可以很好的解决这个问题，但在遍历，定位节点的时候要注意哥不带头结点的链表的区别，这个头结点 只是用来作为前驱存放原本第一个节点的地址的。

public LNode Creat_LinkListTailWithHead() {
        LNode H = null;//头指针
        LNode R = null;//尾指针
        //建立头结点
        LNode headNode = new LNode();
        headNode.next = null;

        H = headNode;
        R = headNode;
        System.out.println("现在使用带头结点的的链表尾部插入，输入0为结束");
        String newDate;
        while(!(newDate=in.next()).equals("0")){
            LNode newNode = new LNode();
            newNode.data =  newDate;
            newNode.next = null;
            R.next = newNode;
            R=newNode;
        }
        R.next = null;
        return H;
    }

遍历链表

遍历的思路是从头结点开始，输出节点的数据， 之后让指针移动到下一个节点

//遍历链表
    public void look(LNode head) {
        if (head == null) {
            System.out.println("链表为空");
            System.exit(0);
        }
        LNode flag = head;//用一个指针来拿到头结点的地址
        do {
            System.out.print(flag.data);
            flag = flag.next;//下移到下一个节点
        } while (flag != null);//如果节点为空结束循环
    }

当然这个遍历是有问题的，没有判断链表有没有带头结点，大家可以自行修改一下。

计算链表长度

这个的思路的遍历差不多，只不过我们需要定义一个变量用来存储长度

//计算带头结点的链表的长度
    public int lenth_haveHead(LNode H){
        int len = 0 ;//用来存放长度
        while(H.next!=null){
            H=H.next;
            len++;
        }
        return len;
    }
    //不带头结点的链表的长度
    public int lenth_nothaveHead(LNode H){
        int len = 0;//用来存放长度
        //判断链表是否为空
        if(H==null){
            System.out.println("链表为空");
            return 0;
        }
        len = 1;
        while(H.next!=null){
            H = H.next;
            len++;
        }
        return len;
    }

可以看出，带头节点的链表在遍历上就比不带的方便很多。

查询指定节点

//查询指定节点
    //n 代表第几个节点
    public LNode findLNode(int n,LNode H){
        LNode myH;
        if(H.data == null){
            //带头结点
            myH = H.next;
        }else{
            //不带头结点
            myH = H;
        }
        int len = 0;
        while(myH!=null){
            len++;
            if(len == n) break;
            myH = myH.next;
        }
        return myH;
    }

首先我们知道带头节点的链表的第一个节点，没有数据，用这个作为标志来判断链表是哪种链表。 

如果是带头结点的，那链表的第一位应该是头结点.next

后排插入

后排插入就是在一个节点的后面，插入一个新节点 
思路如下 

我们先找到这个节点 

通过这个节点的next得到下一个节点的地址，让新节点的next指向下一个节点。 

让被插的节点将next指向新的节点

                                     

下面给出实现代码

//在第n的节点后插入data
    public void insertBehind(String data,int n,LNode H){
        MyLinkList list = new MyLinkList();
        LNode newNode = new LNode();//新建节点
        newNode.data = data;
        newNode.next = null;
        LNode node = list.findLNode(n, H);//找到要插入的位置
        if(node == null) {
            System.out.println("找不到节点");
            return;
        }
        //获取前驱的next，也就是下一个节点
        newNode.next = node.next;
        //让前驱指向新的节点
        node.next = newNode;
    }

前排插入

前排插入的思想和后排插入差不多，只不过我们再拿到节点后，需要再去查找一次，找到这的节点的前驱，之后以这个前驱做后排插入就行了。

/*
     * 在第n个节点前面插入一个节点
     * */
    public void insertFront(String data,int n,LNode H){
        LNode newNode = new LNode();
        newNode.data = data;
        newNode.next = null;
        MyLinkList list = new MyLinkList();
        //找到要插入的节点
        LNode node = list.findLNode(n, H);
        if(node==null){
            System.out.println("找不到节点");
            return;
        }
        //找到node节点的前驱
        LNode myH = H;
        while(myH.next!=node){
            myH = myH.next;
        }
        newNode.next = node;
        myH.next = newNode;
    }

删除节点

删除节点的思路如下： 

找到要删除的节点 

再找到他的前驱节点 

让前驱的next指向这个节点的next，这个时候要删除的节点已经被架空了 

最后我们给这个要删除的节点赋值null 释放空间

                     

MyLinkList list = new MyLinkList();
        LNode node = list.findLNode(n, H);
        if(node == null) {
            System.out.println("找不到要删除的节点");
            return;
        }
        //找到这个节点的前驱
        LNode frontNode = list.findLNode(n-1, H);
        if(frontNode==null){
            System.out.println("找不到前驱");
            return;
        }
        frontNode.next = node.next;
        node = null;
    }

循环链表

循环链表就是将最后一个节点，原来指向空，改成指向头部，实质上并没有什么区别，主要是判断是不能用null来做链表结束的条件了

双向链表

单向的连接再很多时候会有麻烦，比如我们的前排插入，我们要得到前驱，不得不再做一次遍历，双向链表正是为了解决这个问题，我们再结构中再加一个指针让他指向前驱就可以了。

package com.ys.datastructure;

public class TwoWayLinkedList {
    private Node head;//表示链表头
    private Node tail;//表示链表尾
    private int size;//表示链表的节点个数
    
    private class Node{
        private Object data;
        private Node next;
        private Node prev;
        
        public Node(Object data){
            this.data = data;
        }
    }
    
    public TwoWayLinkedList(){
        size = 0;
        head = null;
        tail = null;
    }
    
    //在链表头增加节点
    public void addHead(Object value){
        Node newNode = new Node(value);
        if(size == 0){
            head = newNode;
            tail = newNode;
            size++;
        }else{
            head.prev = newNode;
            newNode.next = head;
            head = newNode;
            size++;
        }
    }
    
    //在链表尾增加节点
    public void addTail(Object value){
        Node newNode = new Node(value);
        if(size == 0){
            head = newNode;
            tail = newNode;
            size++;
        }else{
            newNode.prev = tail;
            tail.next = newNode;
            tail = newNode;
            size++;
        }
    }
    
    //删除链表头
    public Node deleteHead(){
        Node temp = head;
        if(size != 0){
            head = head.next;
            head.prev = null;
            size--;
        }
        return temp;
    }
    
    //删除链表尾
    public Node deleteTail(){
        Node temp = tail;
        if(size != 0){
            tail = tail.prev;
            tail.next = null;
            size--;
        }
        return temp;
    }
    
    //获得链表的节点个数
    public int getSize(){
        return size;
    }
    //判断链表是否为空
    public boolean isEmpty(){
        return (size == 0);
    }
    
    //显示节点信息
    public void display(){
        if(size >0){
            Node node = head;
            int tempSize = size;
            if(tempSize == 1){//当前链表只有一个节点
                System.out.println("["+node.data+"]");
                return;
            }
            while(tempSize>0){
                if(node.equals(head)){
                    System.out.print("["+node.data+"->");
                }else if(node.next == null){
                    System.out.print(node.data+"]");
                }else{
                    System.out.print(node.data+"->");
                }
                node = node.next;
                tempSize--;
            }
            System.out.println();
        }else{//如果链表一个节点都没有，直接打印[]
            System.out.println("[]");
        }
        
    }
}

文章来源：

https://www.cnblogs.com/ysocean/p/7928988.html

https://blog.csdn.net/zjsxxzh/article/details/75102058

写的不错，转来了，其中又补充

链表Link里面其实没什么东西，只需要一个头节点(Node)就足够了

Link.java


public class Link {
	public Node head;
}




在节点(Node)里面需要一个存数据的地方data,data数据类型为Object，将数据域定义成Object类是因为Object类是广义超类，任何类对象都可以给其赋值，增加了代码的通用性。为了使链表可以被访问还需要定义一个表头，表头必须包含指向第一个结点的指针和指向当前结点的指针。为了便于在链表尾部增加结点，还可以增加一指向链表尾部的指针，另外还可以用一个域来表示链表的大小，当调用者想得到链表的大小时，不必遍历整个链表。
然后和存下一个节点的位置Node next;
Node.java


public class Node {
	Object data;
	Node next;
}



TeskLink.java


public class TestLink {
	public static void main(String[] args){
		int[] a = {1,4,5,3,23,45,34,23,123};
		TestLink l = new TestLink();
		Link lk = new Link();
		lk = l.link(a);
		prtLinkedList(lk);
	}
	/**
	 * 将数组转换成链表
	 * @param arr
	 * @return
	 */
	public Link link(int[] arr){
		Link lk = new Link();
		Node nd = new Node();
		//先给链表里第一个node里的data赋值
		nd.data = arr[0];
		//然后将这个node的地址传给Link的head
		lk.head = nd;
		//如果数组还没完，则继续创建新的节点（Node），并传入数组的一个值
		//然后将这个node的地址传给nd的下一个节点nd.next
		//再将下一个节点地址赋值给当前节点nd
		for(int i=1; i<arr.length; i++){
			Node tmp = new Node();
			tmp.data = arr[i];
			nd.next = new Node();
			nd.next = tmp;
			nd = nd.next;//节点移动
		}
 
		return lk;
	}
	/**
	 * 打印链表
	 * @param lk
	 */
	public static void prtLinkedList(Link lk){
		Node nd = new Node();
		nd = lk.head;
		while(nd!=null){
			System.out.print(nd.data+" ");
			nd = nd.next;
		}
	}
}


转自：http://www.zhouwenze.com/archives/20101228-199.html

本文实例讲述了Java链表中添加元素的原理与实现方法。分享给大家供大家参考，具体如下：
1.链表中头节点的引入
1.1基本的链表结构：
1.2对于链表来说，若想访问链表中每个节点则需要把链表的头存起来，假如链表的头节点为head，指向链表中第一个节点，如图：
1.3使用代码表示此时的链表
//定义头节点
private Node head;
//节点个数
private int size;
//无参数构造函数
public LinkedList() {
head = null;
size = 0;
}
//获取链表中的元素个数
public int getSize() {
return size;
}
//返回链表是否为空
public boolean isEmpty() {
return size == 0;
}
2.在链表头添加元素
2.1初始时，假设链表如下：
2.2 如在链表头添加一个666元素则需要先将666放进一个节点里，在节点里存入这个元素以及相应的next。
操作如下：
第一步：现将666这个节点(node)的next指向head,代码如下：
node.next=head
图示为：
第二步：然后再将head指向新的节点666
head=node
图示为：
通过第一步、第二步，我们就成功将新节点添加到头节上。此时node这个变量也就结束了此轮的工作，结果变为：
2.3 在链表头添加新元素的相关代码
//在链表头添加新的元素e
public void addFirst(E e) {
Node node = new Node(e);
node.next = head;
head = node;
size++;
}
等同于：
//在链表头添加新的元素e
public void addFirst(E e) {
head = new Node(e, head);
size++;
}
2.4 在链表中间添加元素
假设初始链表为：
假设我们需要在索引为2的位置添加元素666(此时的索引为2只是用来说明我们此时需要操作的位置，并不是真正的索引意思)
操作步骤：
1)：创建出666这个节点
2)：使用一个变量prev来标识在需要插入节点的地方的前一个节点，初始时prev和头节点head是相同的。
对于此处我们需要在索引为2的位置插入新元素，我们只需要找到索引为2的前一个位置(索引为1)，然后把prev指向索引为1节点即可。
3)：进行元素添加操作
第一步：先将node的next指向prev的下一个节点元素
node.next=prev.next
第二步：再将prev的next指向node
prev.next=node
通过第一步、第二步即可将新元素插入到索引为2的地方。
从上不难看出，对于在链表中添加元素关键是找到要添加的节点的前一个节点，因此对于在索引为0的节点添加元素就需要单独处理。
关于在链表中间添加元素的代码：
//在链表的index(0--based)的位置添加新的元素e  (实际不常用，练习用)
public void add(int index, E e) {
if (index < 0 || index > size) {
throw new IllegalArgumentException("位置不合法");
}
//对于头节点的特殊处理
if (index == 0) {
addFirst(e);
} else {
Node prev = head;
for (int i = 0; i < index - 1; i++) {//获取到需要添加元素位置的前一个元素
prev = prev.next;
}
Node node = new Node(e);
node.next = prev.next;
prev.next = node;
size++;
}
}
此时代码等同于：
//在链表的index(0--based)的位置添加新的元素e  (时间不常用，练习用)
public void add(int index, E e) {
if (index < 0 || index > size) {
throw new IllegalArgumentException("位置不合法");
}
//对于头节点的特殊处理
if (index == 0) {
addFirst(e);
} else {
Node prev = head;
for (int i = 0; i < index - 1; i++) {//获取到需要添加元素位置的前一个元素
prev = prev.next;
}
//      Node node = new Node(e);
//      node.next = prev.next;
//      prev.next = node;
prev.next=new Node(e,prev.next);
size++;
}
}
3.在链表尾部添加元素
这里复用上述的add()方法
//在链表末尾添加新的元素
public void addLast(E e){
add(size,e);
}
本小节完整代码：
package LinkedList;
public class LinkedList {
//将Node节点设计成私有的类中类
private class Node {
public E e;
public Node next;
//两个参数的构造函数
public Node(E e, Node next) {
this.e = e;
this.next = next;
}
//一个参数的构造函数
public Node(E e) {
this.e = e;
this.next = null;
}
//无参构造函数
public Node() {
this(null, null);
}
@Override
public String toString() {
return e.toString();
}
}
//定义头节点
private Node head;
//节点个数
private int size;
//无参数构造函数
public LinkedList() {
head = null;
size = 0;
}
//获取链表中的元素个数
public int getSize() {
return size;
}
//返回链表是否为空
public boolean isEmpty() {
return size == 0;
}
//在链表头添加新的元素e
public void addFirst(E e) {
head = new Node(e, head);
size++;
}
//在链表的index(0--based)的位置添加新的元素e  (实际不常用，练习用)
public void add(int index, E e) {
if (index < 0 || index > size) {
throw new IllegalArgumentException("位置不合法");
}
//对于头节点的特殊处理
if (index == 0) {
addFirst(e);
} else {
Node prev = head;
for (int i = 0; i < index - 1; i++) {//获取到需要添加元素位置的前一个元素
prev = prev.next;
}
//      Node node = new Node(e);
//      node.next = prev.next;
//      prev.next = node;
prev.next=new Node(e,prev.next);
size++;
}
}
//在链表末尾添加新的元素
public void addLast(E e){
add(size,e);
}
}
更多关于java算法相关内容感兴趣的读者可查看本站专题：《Java数据结构与算法教程》、《Java操作DOM节点技巧总结》、《Java文件与目录操作技巧汇总》和《Java缓存操作技巧汇总》
希望本文所述对大家java程序设计有所帮助。