关于java:数据结构单链表-循环链表-双向循环链表-双链表

单链表

如果是null，就阐明前面没有节点了，如果不是null就阐明前面要连贯节点

每个节点蕴含2局部，数据域，和一个指向下一个节点援用的指针next
data域--寄存结点值的数据域
next域--寄存结点的间接后继的地址的指针域（链域）
链表通过每个结点的链域将线性表的n个结点按其逻辑程序链接在一起的，每个结点只有一个链域的链表称为单链表（Single Linked List）。
单链表

显示所有节点信息

头部插入节点
如果链表没有头结点，新结点间接成为头结点；否则新结点的next间接指向以后头结点，并让新结点成为新的头结点。

/*** 增加结点至链表头部** @param value*/public void addHeadNode(T value) {   Node newNode = new Node(value);   //头结点不存在，新结点成为头结点   if (head == null) {       head = newNode;       return;   }   //新结点next间接指向以后头结点   newNode.next = head;   //新结点成为新的头结点   head = newNode;}

尾部插入节点
如果链表没有头结点，新结点间接成为头结点；否则须要先找到链表以后的尾结点，并将新结点插入到链表尾部。

/*** 增加结点至链表尾部** @param value*/public void addTailNode(T value) {   Node newNode = new Node(value);   //头结点不存在，新结点成为头结点   if (head == null) {       head = newNode;       return;   }   //找到最初一个结点   Node last = head;   while (last.next != null) {       last = last.next;   }   //新结点插入到链表尾部   last.next = newNode;}

指定地位插入节点
先判断插入地位为头尾两端的状况，即index == 0插入到头部，index == size()插入到尾部；如果插入地位不是头尾两端，则先找出以后index地位的结点cur以及前一个结点 pre，而后cur成为新结点的下一个结点，新结点成为pre的后一个结点，这样就胜利插入到index地位。

/** * 结点插入至指定地位 * * @param value 结点数据 * @param index 插入地位 */public void addNodeAtIndex(T value, int index) {    if (index < 0 || index > size()) { //留神index是能够等于size()的        throw new IndexOutOfBoundsException("IndexOutOfBoundsException");    }    if (index == 0) {  //插入到头部        addHeadNode(value);//后面定义的办法    } else if (index == size()) {  //插入到尾部        addTailNode(value);//后面定义的办法    } else {  //插到某个两头地位        Node newNode = new Node(value);        int position = 0;        Node cur = head;  //标记以后结点        Node pre = null;  //记录前置结点        while (cur != null) {            if (position == index) {                newNode.next = cur;                pre.next = newNode;                return;            }            pre = cur;            cur = cur.next;            position++;        }    }}

插入一个节点做以后节点的下一个节点

指定地位删除节点
找出以后index地位的结点cur以及前一个结点 pre，pre.next间接指向cur.next即可删除cur结点。

/** * 删除指定地位的结点 * * @param index 指定地位 */public void deleteNodeAtIndex(int index) {    if (index < 0 || index > size() - 1) {        throw new IndexOutOfBoundsException("IndexOutOfBoundsException");    }    if (index == 0) { //删除头        head = head.next;        return;    }    int position = 0;  //记录以后地位    Node cur = head;  //标记以后结点    Node pre = null;  //记录前置结点    while (cur != null) {        if (position == index) {            pre.next = cur.next;            cur.next = null;  //断开cur与链表的连贯            return;        }        pre = cur;        cur = cur.next;        position++;    }}

删除下一个节点
链表反转
在链表遍历的过程中将指针程序置换，即每遍历一次链表就让cur.next指向pre，最初一个结点成为新的头结点。反转之后指针入下图红线所示。

/** * 链表反转 */public void reverse() {    Node cur = head; //标记以后结点    Node pre = null; //标记以后结点的前一个结点    Node temp;    while (cur != null) {        //保留以后结点的下一个结点        temp = cur.next;        //cur.next指向pre，指针程序置换        cur.next = pre;        //pre、cur持续后移        pre = cur;        cur = temp;    }    //最初一个结点变成新的头结点    head = pre;}

求倒数第k个结点
倒数第k个结点就是第size() - k + 1个结点，cur结点向后挪动size() - k次就是倒数第k个结点。

/** * 倒数第k个结点 * * @param k * @return */public T getLastK(int k) {    if (k < 0 || k > size()) { //留神index是能够等于size()的        throw new IndexOutOfBoundsException("IndexOutOfBoundsException");    }    Node cur = head;    for (int i = 1; i < size() - k + 1; i++) {        cur = cur.next;    }    return cur.value;}

单链表

循环链表

双链表

循环双向列表