链表是一系列的存储数据元素的单元通过指针串起来形成的,因此每个单元至少有两个域，一个域用于数据元素的存储，另一个域是指向其他单元的指针。这里具有一个数据域和多个指针域的存储单元通常称为节点（node）。
一种最简单的节点结构如图所示：
它是构成单链表的基本节点结构，在节点中数据域用来存储数据元素，指针域用于指向下一个具有相同构成的节点。（因为其只有一个指针节点，称为单链表）。
链表的第一个节点和最后一个节点，分别称为链表的首节点和尾结点，尾结点的特征为next 为 null。
带头结点的链表，头结点不存放有效数据，next指向第一个有效结点。
初始化头结点head如下：
插入结点：
- 头插法：
public void addHead(E ele){ //创建一个新节点 Node newNode = new Node(ele,null); //新节点的直接后继 newNode.next = head.next;
//新节点的前驱为head head.next = newNode; size++; //记录有效元素的个数 }初始只有一个头结点，head.next 为null,新创建的结点的next应该指向head的next域。插入第一个节点：
插入第二个结点：
2.选定位置插入结点元素
public void add(int index,E element){ //找到前一个节点，从头结点开始 Node p = head; //判断参数合法性 if(index < 0 || index > size){ throw new RuntimeException("参数不合法！"); }else { for (int j = 0; j < index; j++) { p = p.next; } } //创建一个新节点 Node newNode = new Node(element, null); //新节点的直接后继 newNode.next = p.next; //新节点的直接前驱 p.next = newNode; size++; }
size为有效元素的个数，加入要插入到index = 2 的位置，应该先找到其前驱结点，即1号位置，（当for循环两次之后，其P指针所在的位置如图）
创建新节点，找到其直接前驱和直接后继，便插入成功。
3.尾插法
尾插法便是指定位置插入数据的特殊情况，具体实现见代码。
package 线性表; public class MyLinkList<E> { private Node<E> head; //节点数 private int size; public MyLinkList(){ //初始化head 结点 this.head = new Node<E>((E)new Object(),null); } class Node<E> { E data; //要存储的数据 Node next; //引用 public Node(E data) { this.data = data; } public Node(E data, Node next) { this.data = data; this.next = next; } } /** * 得到节点个数 * @return */ public int size(){ return size; } /** * * @param index * @return */ public E get (int index) { //需要从头节点开始查找 //定义一个引用 Node p = head; if (index < 0 || index >= size) { throw new RuntimeException("参数不合法！"); } else { for (int i = 0; i <= index; i++) { p = p.next; } } return (E) p.data; } /** * 判断是否为空 * @return */ public boolean empty(){ return size == 0; } /** * 指定位置添加元素 * @param index * @param element */ public void add(int index,E element){ //找到前一个节点，从头结点开始 Node p = head; //判断参数合法性 if(index < 0 || index > size){ throw new RuntimeException("参数不合法！"); }else { for (int j = 0; j < index; j++) { p = p.next; } } //创建一个新节点 Node newNode = new Node(element, null); //新节点的直接后继 newNode.next = p.next; //新节点的直接前驱 p.next = newNode; size++; } /** * 头插法添加元素 * @param ele */ public void addHead(E ele){ //创建一个新节点 Node newNode = new Node(ele,null); //新节点的直接后继 newNode.next = head.next; head.next = newNode; size++; } /** * 尾插法 * @param ele */ public void addTail(E ele){ this.add(size,ele); } /** * 删除指定位置元素 * @param index */ public void delete(int index){ //从头节点开始遍历 Node p = head; //找到该节点的前一个结点 if(index < 0 || index > size){ throw new RuntimeException("参数不合法！"); }else { for (int i = 0; i < index; i++) { p = p.next; } //改变指向 p.next = p.next.next; //更新节点数 size--; } } public void show(){ Node p = head; for (int i = 0; i < size; i++) { p = p.next; System.out.print(p.data + " "); } } }
package 线性表; public class MyLinkListTest { public static void main(String[] args) { MyLinkList<Integer> ml = new MyLinkList<>(); ml.addHead(1); ml.add(1,3); ml.addHead(2); ml.addHead(5); ml.addTail(6); ml.delete(0); System.out.println(ml.empty()); System.out.println(ml.get(0)); System.out.println(ml.get(1)); ml.show(); } }
结果如图：
