Java数据结构——单向链表实现

 /** * 单向链表实现类 * @Description * 类描述： * @author GaoAnQiu * @Date * @modify * 修改记录： * */ public class Link { private int size = 0; private Node first; private Node last; public Node getFirst() { return first; } public void setFirst(Node first) { this.first = first; } public Node getLast() { return last; } public void setLast(Node last) { this.last = last; } public Link() { } /** * 返回链表长度 * @Description * 方法描述: * @return 返回类型： int * @return */ public int getLength() { return size; } public void printLink(Link link) { Node temp = first; while (temp != null) { System.out.print(temp.getData() + "-->"); temp = temp.getNext(); } System.out.println(); } /** * 返回指定位置的节点 * @Description * 方法描述: * @return 返回类型： Node * @param index * @return */ public Node get(int index) { Node temp = first; for (int i = 0; i < index; i++) { temp = temp.getNext(); } return temp; } /** * 插入第一个元素，头和尾都指向同一个元素 * @Description * 方法描述: * @return 返回类型： void */ private void onetNode(int element) { first = new Node(); first.setData(element); last = first; } public void addHead(int element) { if (size == 0) { onetNode(element); } else { Node node = new Node(); node.setData(element); node.setNext(first); first = node; } size++; } /** * 插入尾结点 * @Description * 方法描述: * @return 返回类型： void * @param element */ public void addTail(int element) { if (size == 0) { onetNode(element); } else { Node node = new Node(); node.setData(element); last.setNext(node); last = node; //将插入的结点设置为尾结点 size++; } } /** * 插入中间元素 * 头尾两处需要特殊处理 * @Description * 方法描述: * @return 返回类型： void * @param index * @param element */ public void add(int index, int element) { if (index > size) { throw new IndexOutOfBoundsException("待插入的位置超过链表的最大长度。"); } else { if (index == 0) { //下标为0时，插入头元素 addHead(element); } else if (size == index) { //下标与链表长度一致时，插入尾元素 addTail(element); } else { Node preNode = get(index - 1); // Node nextNode = get(index); Node newNode = new Node(); newNode.setData(element); preNode.setNext(newNode); newNode.setNext(nextNode); size++; } } } /** * 删除头节点 * @Description * 方法描述: * @return 返回类型： void */ public void delHead() { if (size == 0) { throw new IndexOutOfBoundsException("空链表，无元素可删除"); } else { if (size == 1) { //只有一个节点时，清空链表 clear(); } else { Node nextNode = first.getNext(); first = nextNode; } size--; } } /** * 清空链表 * @Description * 方法描述: * @return 返回类型： void */ public void clear() { first = last = null; size = 0; } public void delTail() { if (size == 0) { throw new IndexOutOfBoundsException("空链表，无可删除的元素。"); } else if (size == 1) { clear(); } else { //取出尾节点的前一个节点，next赋值为null Node preTail = get(size - 2); preTail.setNext(null); last = preTail; size--; } } /** * 删除节点 * @Description * 方法描述: * @return 返回类型： void * @param index */ public void del(int index) { if (index >= size) { throw new IndexOutOfBoundsException("删除位置越界"); } else { if (index == 0) { delHead(); } else if (index == size - 1) { delTail(); } else { Node preNode = get(index - 1); Node nextNode = get(index + 1); preNode.setNext(nextNode); size--; } } } } 

 public class Node { private int data;//数据 private Node next;//指针 public int getData() { return data; } public void setData(int data) { this.data = data; } public Node getNext() { return next; } public void setNext(Node next) { this.next = next; } }