双向链表及循环链表

双向链表

双链表和单链表相比，多了一个指向尾指针（tail），双链表的每个结点都有一个头指针head和尾指针tail,双链表相比单链表更容易操作，双链表结点的首结点的head指向为null，tail指向下一个节点的tail;尾结点的head指向前一个结点的head，tail 指向为null，是双向的关系

双向链表代码

import java.util.Iterator;

public class TwoWayLink implements Iterable {

  Node head = null;
  Node tail = null;

  int size;

  class Node {
    Node next = null;
    Node previous = null;
    int data;

    public Node(int data) {
      this.data = data;
    }

    @Override
    public String toString() {
      return "data:" + data;
    }
  }

  public void addNode(int d) {
    Node newNode = new Node(d);
    if (head == null) {
      head = newNode;
      tail = newNode;
      size = 1;
      return;
    }

    Node tailTmp = tail;
    tailTmp.next = newNode;
    newNode.previous = tailTmp;
    tail = newNode;
    size++;
  }

  public Node getNode(int index) {
    if (index == 0) {
      return head;
    }
    if (index + 1 == size) {
      return tail;
    }
    int i = 1;
    Node curNode = head.next;
    while (curNode != null) {
      if (i == index) {
        return curNode;
      }
      curNode = curNode.next;
      i++;
    }
    return null;
  }

  public Node removeNode(Node remove) {
    Node previous = remove.previous;
    Node next = remove.next;
    if (remove.equals(head)) {
      next.previous = null;
      head = next;
    } else if (remove.equals(tail)) {
      previous.next = null;
      tail = previous;
    } else {
      previous.next = next;
      next.previous = previous;
    }
    size--;
    return remove;
  }

  public int size() {
    return size;
  }

  @Override
  public Iterator iterator() {
    return new Iterator() {
      int cursor;
      int lastRet = -1;

      @Override
      public boolean hasNext() {
        return cursor != size;
      }

      @Override
      public Object next() {
        lastRet = cursor;
        cursor++;
        return getNode(lastRet);
      }
    };
  }

  public static void main(String[] args) {
    TwoWayLink twoWayLink = new TwoWayLink();
    twoWayLink.addNode(1);
    twoWayLink.addNode(2);
    twoWayLink.addNode(3);
    System.out.println(twoWayLink.size());
    Iterator iterator = twoWayLink.iterator();
    while (iterator.hasNext()) {
      System.out.println(iterator.next());
    }
  }
}

循环链表

节点自身数值data以及所指向的下一个节点next

package circularLinkedList;
 
public class Node {
	//元素类型为int的节点
	private int data;
	private Node next;
	//定义构造器
	public Node(int i, Node nt){
		data = i;
		next = nt;
	}
	public Node(int i){
		this(i,null);
	}
	public Node(){
		this(0,null);
	}
	//更改元素数值
	public void setData(int i){
		data = i;
	}
	//读取元素数值
	public int getData(){
		return data;
	}
	//更改元素的指向
	public void setNext(Node nt){
		next = nt;
	}
	//读取元素的指向
	public Node getNext(){
		return next;
	}

关键要素是指定链表的头节点head、尾节点tail以及链表大小size；该数据结构支持在头部增加节点、在尾部增加节点，从头部删除节点及从尾部删除节点

package circularLinkedList;
 
public class Linkedlst {
	private Node head;
	private Node tail;
	int size;
	//构造器
	public Linkedlst(){
		tail = head = null;
		size = 0;
	}
	
	//在链表头部增加节点
	public void addHead(Node hd){
	//如果使用该方法增加链表的第一个节点，则head=tail=hd，且next指向自身。
		if(size==0){
			hd.setNext(hd);
			tail = head = hd;
			size++;
		}
		else{
				tail.setNext(hd);
				hd.setNext(head);
				head = hd;
				size++;
		}
	}
	
	//在链表尾部增加节点
	public void addTail(Node tl){
	//如果使用该方法增加链表的第一个节点，则tail=head= hd，且next指向自身。
		if(size==0){
			tl.setNext(tl);
			tail = head = tl;
			size++;
		}
		else{
			tail.setNext(tl);
			tl.setNext(head);
			tail = tl;
			size++;
		}
	}
	
	//删除头部节点，被删掉的head将被自动回收
	public void delHead(){
		if(size>1){
			head = head.getNext();
			tail.setNext(head);
			size--;
		}
		else if(size==1){
			head = tail = null;
			size--;
		}
		else{
			System.out.println("There is no elements in the linked list.");
		}
	}
	
	//删除尾部节点
	public void delTail(){
		if(size>1){
			Node nd = new Node();
			nd = head;
			while(nd.getNext()!=tail){
				nd = nd.getNext();
			}
			nd.setNext(head);
			size--;
		}
		else if(size==1){
			head = tail = null;
			size--;
		}
		else{
			System.out.println("There is no elements in the linked list.");
		}		
	}
	
	//打印全部节点
	public void printList(){
		Node nd = new Node();
		nd = head;
		try{
			while(nd.getNext()!=head){
				System.out.print(nd.getData());
				System.out.print("->");
				nd = nd.getNext();
			}		
			System.out.print(nd.getData());
			System.out.print("->");
			System.out.print(head.getData());
		}
		catch(Exception e){			
			e.printStackTrace();
		}
		
	}
}

原文：https://blog.csdn.net/elecjack/article/details/51019875