链表是一种物理存储单元上非连续的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列的结点（链表中的每一个元素称为结点）组成，结点可以在运行时动态生成。
结点API设计
结点类实现:
//结点类 public class Node<T> { //存储元素 public T element; //指向下一个节点 public Node next; public Node(T element,Node next){ this.element=element; this.next=next; } }
生成链表
public static void main(String[] args) { //构建结点 Node<Integer> first=new Node<Integer>(5,null); Node<Integer> second=new Node<Integer>(6,null); Node<Integer> third=new Node<Integer>(7,null); Node<Integer> fourth=new Node<Integer>(7,null); Node<Integer> fifth=new Node<Integer>(7,null); //生成链表 first.next=second; second.next=third; third.next=fourth; fourth.next=fifth; }
单向链表
单向链表是链表的一种，它由多个结点组成，每个结点都由一个数据域和一个指针域组成，数据域用来存储数据，指针域用来指向其后继结点。链表的头结点的数据域不存储数据，指针域指向第一个真正存储数据的结点。
单向链表API设计
代码实现:
public class LinkList<T> implements Iterable<T> { //记录头结点 private Node head; //记录链表的长度 private int N; public LinkList(){ //初始化头结点 head=new Node(null,null); N=0; } //清空链表 public void clear(){ head.next=null; head.element=null; N=0; } //链表长度 public int length(){ return N; } //判断链表是否为空 public boolean isEmpty(){ return N==0; } //获取i处的元素 public T get(int i){ if(i<0||i>=N){ throw new RuntimeException("位置不合法"); } Node n=head.next; for(int index=0;index<i;index++){ n=n.next; } return n.element; } //向链表中添加元素t public void inset(T t){ //找到最后一个结点 Node n=head; while(n.next!=null){ n=n.next; } Node newNode=new Node(t,null); n.next=newNode; //链表长度+1 N++; } //向指定位置i处，添加元素t public void insert(int i,T t){ if(i<0||i>N){ throw new RuntimeException("位置不合法"); } //寻找位置i之前的结点 Node pre=head; for(int index=0;index<=i-1;index++){ pre=pre.next; } //位置i的结点 Node curr=pre.next; //构建新的结点,让新结点指向位置i的结点 Node newNode=new Node(t,curr); //让之前的结点指向新结点 pre.next=newNode; //长度+1 N++; } //删除指定位置i处的元素,并返回被删除的元素 public T remove(int i){ if(i<0||i>=N){ throw new RuntimeException("位置不合法"); } Node pre=head; for(int index=0;index<=i-1;index++){ pre=pre.next; } //当前i位置的结点 Node curr=pre.next; //前一个结点指向下一个结点，删除当前结点 pre.next=curr.next; //长度-1 N--; return (T) curr.element; } //查找t元素在链表中第一次出现的位置 public int indexOf(T t){ Node n=head; for(int i=0;n.next!=null;i++){ n=n.next; if(n.element.equals(t)){ return i; } } return -1; } private class Node { //存储元素 T element; //指向下一个节点 Node next; public Node(T element, Node next) { this.element = element; this.next = next; } } @Override public Iterator iterator(){ return new LIterator(); } private class LIterator implements Iterator<T>{ private Node n; public LIterator(){ this.n=head; } @Override public boolean hasNext(){ return n.next!=null; } @Override public T next(){ n=n.next; return n.element; } } } class Test{ public static void main(String[] args) throws Exception{ LinkList<String> list=new LinkList<>(); list.insert(0,"龍龍"); list.insert(1,"龍哥"); list.insert(2,"龍"); list.insert(3,"龍"); //测试length方法 for(String s: list){ System.out.println(s); } System.out.println(list.length()); System.out.println("------------"); //测试get方法 System.out.println(list.get(2)); System.out.println("------------"); //测试remove方法 String remove=list.remove(1); System.out.println(remove); System.out.println("---------------------"); for(String s:list){ System.out.println(s); } } }
