链表：是一种物理存储结构上非连续存储结构。

无头单向非循环链表示意图：

下面就来实现这样一个无头单向非循环的链表。

public void addFirst(int elem) { LinkedNode node = new LinkedNode(elem); //创建一个节点 if(this.head == null) { //空链表 this.head = node; return; } node.next = head; //不是空链表，正常情况 this.head = node; return; }2.尾插法

public void addLast(int elem) { LinkedNode node = new LinkedNode(elem); if(this.head == null) { //空链表 this.head = node; return; } LinkedNode cur = this.head; //非空情况创建一个节点找到最后一个节点 while (cur != null){ //循环结束，cur指向最后一个节点 cur = cur.next; } cur.next = node; //将插入的元素放在最后节点的后一个 }3.任意位置插入,第一个数据节点为0号下标

public void addIndex(int index,int elem) { LinkedNode node = new LinkedNode(elem); int len = size(); if(index < 0 || index > len) { //对合法性校验 return; } if(index == 0) { //头插 addFirst(elem); return; } if(index == len) { //尾插 addLast(elem); return; } LinkedNode prev = getIndexPos(index - 1); //找到要插入的地方 node.next = prev.next; prev.next = node; }

计算链表长度的方法：

public int size() { int size = 0; for(LinkedNode cur = this.head; cur != null; cur = cur.next) { size++; } return size; }

找到链表的某个位置的方法：

private LinkedNode getIndexPos(int index) { LinkedNode cur = this.head; for(int i = 0; i < index; i++){ cur = cur.next; } return cur; }4.查找关键字toFind是否包含在单链表当中

public boolean contains(int toFind) { for(LinkedNode cur = this.head; cur != null; cur = cur.next) { if(cur.data == toFind) { return true; } } return false; }5.删除第一次出现关键字为key的节点

public void remove(int key) { if(head == null) { return; } if(head.data == key) { this.head = this.head.next; return; } LinkedNode prev = seachPrev(key); LinkedNode nodeKey = prev.next; prev.next = nodeKey.next; }

删除前应该先找到找到要删除元素的前一个元素：

private LinkedNode seachPrev(int key){ if(this.head == null){ return null; } LinkedNode prev = this.head; while (prev.next != null){ if(prev.next.data == key){ return prev; } prev = prev.next; } return null; }6.删除所有值为key的节点

public void removeAllkey(int key){ if(head == null){ return; } LinkedNode prev = head; LinkedNode cur = head.next; while (cur != null){ if(cur.data == key){ prev.next = cur.next; cur = prev.next; } else { prev = cur; cur = cur.next; } } if(this.head.data == key){ this.head = this.head.next; } return; }7.打印单链表

public void display(){ System.out.print("["); for(LinkedNode node = this.head; node != null; node = node.next){ System.out.print(node.data); if(node.next != null){ System.out.print(","); } } System.out.println("]"); }8.清空单链表

public void clear(){ this.head = null; }