链表的实现

数据结构：

一个链表是由一个个节点连接而成，每一个结点又包含数据和指向下一节点的指针；还需要一个计数器，记录节点的个数；对于不同的实现可能对头结点有不同的要求，比如头结点直接就是指向第一个元素，或者设置一个虚拟头结点，不存储任何值，直接指向链表的第一个元素。

带头结点：

首先需要有一个节点类，类中应该包含指向下一个节点的指针，在Java中就是引用，还应该有一个当前节点存储的元素。

然后需要一个链表创建类，类中应该包含头结点，和链表中节点的数量。

节点类采用内部类的方式，因为链表如何实现的并不需要要对用户开放，用户只需要使用到链表的功能即可。

实现代码如下：

public class LinkedList<E> { /* * 内部类实现节点 * */ private class Node{ //这设计成public使得外部类能直接访问 public E e; public Node next; public Node(E e, Node next){ this.e = e; this.next = next; } //初始化时有一个元素 public Node(E e){ this(e,null); } //初始化时没有元素 public Node(){ this(null,null); } //重写toString()方法 @Override public String toString() { return e.toString(); } } private Node head; private int size; //初始化链表，头指针为空，元素个数为0 public LinkedList(){ head = null; size = 0; } /* * 获取链表中的元素的个数 * */ public int getSize(){ return size; } /* * 判断链表是否为空 * */ public boolean isEmpty(){ return size == 0; } /* * 向链表中指定位置添加一个节点 * Java类库中并不会这样添加节点,类库中是在链表末尾添加节点 * 此处只是实现这样实现而已 * */ public void addNode(int index, E e){ if (index < 0 || index > size) throw new IllegalArgumentException("Add failed.Illegal index."); if (index == 0) addFirst(e); else { Node prev = head; for (int i = 0; i < index - 1; i++) prev = prev.next; //插入节点 // Node node = new Node(e); // node.next = prev.next; // prev.next = node; prev.next = new Node(e, prev.next); size++; } } /* * 向链表头部增加节点 * */ public void addFirst(E e){ /*Node node = new Node(e); node.next = head; head = node;*/ head = new Node(e,head); size++; } /* * 向链表末尾添加元素 * */ public void addLast(E e){ /*Node temp = head; while (temp.next !=null) temp = temp.next; temp.next = new Node(e, temp.next);*/ addNode(size, e); } /** * @Author Dragon * @Description 删除指定元素 * @Date 18:46 2019/6/4 * @Param [e] * @return boolean **/ public boolean removeElement(E e){ boolean flag = false; while (head != null && head.e == e){ Node delNode = head; head = head.next; delNode.next = null; flag = true; return flag; } if (head == null){ flag = true; return flag; } Node prev = head; while (prev.next != null){ if (prev.next.e == e){ /* Node delNode = prev.next; prev.next = delNode.next; delNode.next = null;*/ prev.next = prev.next.next; //只是跳过了要被删除的节点，内存没有释放 flag = true; break; } prev = prev.next; } return flag; } @Override public String toString() { StringBuilder rb = new StringBuilder(); rb.append("LinkedList{ "); Node curr = head; while (curr != null){ rb.append(curr.e + "->"); curr = curr.next; } rb.append("NULL }"); return rb.toString(); } }

虚拟头结点：

节点类和带头结点一样，链表类中的头结点换位虚拟头结点，虚拟头结点不存储任何元素，它指向链表的第一个元素。

代码如下：

public class DummyHeadLinkedList<E> { /* * 内部类实现节点 * */ private class Node{ //这设计成public使得外部类能直接访问 public E e; public Node next; public Node(E e, Node next){ this.e = e; this.next = next; } public Node(E e){ this(e,null); } public Node(){ this(null,null); } @Override public String toString() { return e.toString(); } } private Node dummyHead; private int size; public DummyHeadLinkedList(){ dummyHead = new Node(null, null); size = 0; } /* * 获取链表中的元素的个数 * */ public int getSize(){ return size; } /* * 判断链表是否为空 * */ public boolean isEmpty(){ return size == 0; } /* * 向链表中任意位置之后添加一个节点 * Java类库中并不会这样添加节点,类库中是在链表末尾添加节点 * */ public void addNode(int index, E e){ if (index < 0 || index > size) throw new IllegalArgumentException("Add failed.Illegal index."); Node prev = dummyHead; //从第一个节点前的那个虚拟节点开始遍历，所以需要遍历到index位置 for (int i = 0; i < index; i++) prev = prev.next; //插入节点 // Node node = new Node(e); // node.next = prev.next; // prev.next = node; prev.next = new Node(e, prev.next); size++; } /* * 向链表头增加节点 * */ public void addFirst(E e){ /*Node node = new Node(e); node.next = head; head = node;*/ addNode(0,e); /* head = new Node(e,head); size++;*/ } /* * 向链表末尾添加元素 * */ public void addLast(E e){ /*Node temp = head; while (temp.next !=null) temp = temp.next; temp.next = new Node(e, temp.next);*/ addNode(size, e); } /* * 获得链表的某一个位置的元素,位置和下标差1 * 链表中不常用方法，练习 * */ public E get(int index){ if (index < 0 || index > size) throw new IllegalArgumentException("Add failed.Illegal index."); Node curr = dummyHead.next; for (int i = 0; i < index; i++) curr = curr.next; return curr.e; } /* * 获得链表的第一个位置的元素 * */ public E getFirst(){ return get(0); } /* * 获得链表的最后一个位置的元素 * */ public E getLast(){ return get(size - 1); } /* * 修改链表中的某一个元素 * */ public void set(int index, E e){ if (index < 0 || index > size) throw new IllegalArgumentException("Add failed.Illegal is index."); Node curr = dummyHead.next; for (int i = 0; i < index; i++) curr = curr.next; curr.e = e; } /* * 查找链表中的某一个元素是否存在 * */ public boolean contains(E e){ Node curr = dummyHead.next; while (curr != null){ if (curr.e.equals(e)) return true; curr = curr.next; } return false; } /* * 在链表中删除某一个元素 * */ public boolean removeElement(E e){ Node delNode = dummyHead.next; Node prev = null; boolean flag = false; while (delNode != null){ if (delNode.e.equals(e)){ prev.next = delNode.next; delNode = null; flag = true; size--; break; } prev = delNode; delNode = delNode.next; } return flag; } /* * 在链表中删除某一个位置的元素 * */ public E removeIndex(int index){ if (index < 0 || index >= size) throw new IllegalArgumentException("Remove failed.Illegal is index."); Node delNode = dummyHead.next; Node prev = null; E temp = null; for (int i = 0; i < index; i++){ prev = delNode; delNode = delNode.next; } temp = delNode.e; prev.next = delNode.next; delNode = null; size--; return temp; } /* * 在链表中删除某一个位置的元素 * */ public E removeIndexYouHua(int index){ if (index < 0 || index >= size) throw new IllegalArgumentException("Remove failed.Illegal is index."); Node prev = dummyHead; E temp = null; for (int i = 0; i < index; i++) prev = prev.next; Node delNode = prev.next; prev.next = delNode.next; temp = delNode.e; delNode = null; size--; return temp; } /* * 删除第一个元素 * */ public E removeFirst(){ return removeIndexYouHua(0); } /* * 删除最后一个元素 * */ public E removeLast(){ //位置和元素个数差1，所以最后一个元素的位置是size - 1 return removeIndexYouHua(size - 1); } /* * 遍历链表 * */ @Override public String toString() { StringBuilder res = new StringBuilder(); res.append("LinkedList: ["); Node nextN = dummyHead.next; while (nextN != null){ res.append(nextN.e); res.append("->"); /*if(nextN.next != null) res.append(", ");*/ nextN = nextN.next; } res.append("NULL"); return res.toString(); } }