Java实现单链表_使用链式存储结构
单链表的示意图：
贴代码，部分代码参考：
package hash;/** * Created with IntelliJ IDEA. * User: ASUS * Date: 14-9-15 * Time: 下午6:58 * To change this template use File | Settings | File Templates. */public class CustomLinkedList01{ /** * 用来表示单链表的节点类 * class node * * @param * @author egg */ private static class Node { T data; Node next; Node(T data, Node next) { this.data = data; this.next = next; } Node(T data) { this(data, null); } Node() { } } //头指针指向头结点 //头结点的数据域不存储数据 private Node head; //单链表的头节点 //初始化链表，初始化后的链表为空 public CustomLinkedList01() { head = new Node (); //头结点 } /** * judge the list is empty * 除头结点外没有其他节点，该链表为空 */ public boolean isEmpty() { return head.next == null; } /** * 打印链表 * print the list */ public void traverse() { Node p = head.next; for (Node n = p; n != null; n = n.next) System.out.println(n.data); } /** * insert node from head * 头插法 */ public void addFromHead(T item) { Node newNode = new Node (item); //实例化一个节点 Node p = head.next; head.next = newNode; newNode.next = p;//新节点的后继元素原来的head } /** * 尾插法 * insert node from tail */ public void addFromTail(T item) { Node newNode = new Node (item); //实例化一个新节点 Node p = head; while (p.next != null) { //遍历到单链表的尾 p = p.next; } p.next = newNode; //尾节点的后继节点为新节点 newNode.next = null; //新节点的后继节点为空 } /** * delete node from head */ public void removeFromHead() { if (!isEmpty()) { Node p = head.next; //删除第一个节点 head.next = p.next; } else { System.out.println("The list have been emptied!"); } } /** * delete tail, lower effect * 删除最后一个节点 */ public void removeFromTail() { if (isEmpty()) { System.out.println("The list have been emptied!"); } else { //如果curr.next == null说明curr为最后一个节点 Node prev = head, curr = head.next; while (curr.next != null) { prev = curr; curr = curr.next; } prev.next = null; } } /** * insert a new node * 在元素前面插入item * * @param appointedItem * @param item * @return */ public boolean insertBefore(T appointedItem, T item) { Node prev = head, curr = head.next, newNode; newNode = new Node (item); //当到达尾节点或找到元素，跳出循环 while ((curr != null) && (!appointedItem.equals(curr.data))) { prev = curr; curr = curr.next; // 如果到达链表的尾端，说明没有找到插入点 if (curr == null) { return false; } } newNode.next = curr; prev.next = newNode; return true; } /** * insert a new node * * @param appointedItem * @param item * @return */ public boolean insertAfter(T appointedItem, T item) { Node newNode = new Node (item); Node curr = head.next; //当到达尾节点或找到元素，跳出循环 while ((curr != null) && (!appointedItem.equals(curr.data))) { curr = curr.next; if (curr == null) { return false; } } Node p = curr.next; newNode.next = p; curr.next = newNode; return true; } /** * 删除节点 * * @param item */ public void remove(T item) { Node curr = head.next, prev = head; while (curr != null) { if (item.equals(curr.data)) { prev.next = curr.next; return; } else { prev = curr; curr = curr.next; } } } /** * 通过遍历整个链表查找元素 * * @param item * @return */ public int indexOf(T item) { int index = 0; for (Node p = head.next; p != null; p = p.next) { if (item.equals(p.data)) { return index; } index++; } return -1; } /** * judge the list contains one data */ public boolean contains(T item) { return indexOf(item) != -1; } public static void main(String args[]) { CustomLinkedList01 linkedList = new CustomLinkedList01(); linkedList.addFromHead("s1"); linkedList.addFromHead("s2"); linkedList.addFromHead("s3"); linkedList.addFromHead("s4"); linkedList.addFromHead("s5"); linkedList.addFromHead("s6"); linkedList.addFromTail("s00"); linkedList.addFromTail("s01"); linkedList.addFromTail("s02"); System.out.println(linkedList.contains("s03")); System.out.println("#############insertBefore###############"); linkedList.remove("s1"); linkedList.traverse(); System.out.println("#############insertBefore###############"); linkedList.insertBefore("s3", "mm"); linkedList.insertBefore("s02", "mm"); linkedList.traverse(); System.out.println("#############insertAfter###############"); linkedList.insertAfter("mm", "uu"); linkedList.insertAfter("uu", "pp"); linkedList.traverse(); System.out.println("#############removeFromHead###############"); linkedList.removeFromHead(); linkedList.traverse(); System.out.println("#############removeFromTail###############"); linkedList.removeFromTail(); linkedList.traverse(); System.out.println("#############removeFromTail###############"); linkedList.removeFromTail(); linkedList.traverse(); }}
在Java中，linkedList是这样一种存储结构
示例代码如下，
package hash;public class LinkedList{ /** * class node * * @param * @author egg */ private static class Node { T data; Node next; Node(T data, Node next) { this.data = data; this.next = next; } Node(T data) { this(data, null); } } // data private Node head, tail; public LinkedList() { head = tail = null; } /** * judge the list is empty */ public boolean isEmpty() { return head == null; } /** * add head node */ public void addHead(T item) { head = new Node (item); if (tail == null) tail = head; } /** * add the tail pointer */ public void addTail(T item) { if (!isEmpty()) { tail.next = new Node (item); tail = tail.next; } else { head = tail = new Node (item); } } /** * print the list */ public void traverse() { if (isEmpty()) { System.out.println("null"); } else { for (Node p = head; p != null; p = p.next) System.out.println(p.data); } } /** * insert node from head */ public void addFromHead(T item) { Node newNode = new Node (item); newNode.next = head; head = newNode; } /** * insert node from tail */ public void addFromTail(T item) { Node newNode = new Node (item); Node p = head; while (p.next != null) p = p.next; p.next = newNode; newNode.next = null; } /** * delete node from head */ public void removeFromHead() { if (!isEmpty()) head = head.next; else System.out.println("The list have been emptied!"); } /** * delete frem tail, lower effect */ public void removeFromTail() { Node prev = null, curr = head; while (curr.next != null) { prev = curr; curr = curr.next; if (curr.next == null) prev.next = null; } } /** * insert a new node * * @param appointedItem * @param item * @return */ public boolean insert(T appointedItem, T item) { Node prev = head, curr = head.next, newNode; newNode = new Node (item); if (!isEmpty()) { while ((curr != null) && (!appointedItem.equals(curr.data))) { prev = curr; curr = curr.next; } newNode.next = curr; prev.next = newNode; return true; } return false; } public void remove(T item) { Node curr = head, prev = null; boolean found = false; while (curr != null && !found) { if (item.equals(curr.data)) { if (prev == null) removeFromHead(); else prev.next = curr.next; found = true; } else { prev = curr; curr = curr.next; } } } public int indexOf(T item) { int index = 0; Node p; for (p = head; p != null; p = p.next) { if (item.equals(p.data)) return index; index++; } return -1; } /** * judge the list contains one data */ public boolean contains(T item) { return indexOf(item) != -1; }}
=====END=====