java单链表-带头结点和不带头结点单链表的简单实现
带头结点的单链表实现
public class LinkedList<T> {private Entry<T> head, tail; //头指针，尾指针 private int size; //通过一个变量记录链表长度 public LinkedList() { //生成一个头结点,让头指针和尾指针都指向它 head = tail = new Entry<T>(null);size = 0;}public int size() {return size;}public boolean isEmpty() {return head.next == null; //当头结点的next为空,表明整个链表为空}public T get(int index) {return current(index).element;}public T set(int index, T element) {Entry<T> entry = current(index);T oldVal = entry.element;entry.element = element;return oldVal;} //默认在原链表尾部添加新的结点public boolean add(T element) {Entry<T> newEntry = new Entry<T>(element);tail.next = newEntry;//原链表尾指针的next指向新的结点 tail = newEntry;//尾指针向后移动一位，指向新的结点 size++;return true;}public boolean add(int index, T element) { //若索引值和链表长度一样，新结点添加到链表最后位置 if (index == size)return add(element); //得到索引index的前一个结点Entry<T> preEntry = previous(index); //新结点的next为preEntry的next指向的结点Entry<T> newEntry = new Entry<T>(element, preEntry.next); //preEntry的next指向新的结点preEntry.next = newEntry;size++;return true;}public T remove(int index) { //得到索引index的前一个结点Entry<T> preEntry = previous(index);T oldVal = preEntry.next.element; //如果preEntry的next刚好是最后一个结点，修改tail为preEntry if (preEntry.next == tail)tail = preEntry;preEntry.next = preEntry.next.next;size--;return oldVal;}public void clear() {head.next = null;tail = head;size = 0;}public String toString() {String result = "[";Entry<T> entry = head.next;while (entry != null) {result += entry.element;entry = entry.next;if (entry != null)result += ", ";}return result + "]";} //获得索引index对应的entry public Entry<T> current(int index) {checkIndexBounds(index);Entry<T> entry = head.next;//从第一个结点开始遍历int c = 0;while (entry != null && c < index) {entry = entry.next;c++;}return entry;} //获得索引index-1对应的entry public Entry<T> previous(int index) {checkIndexBounds(index);Entry<T> entry = head;//从头结点开始遍历，头指针指向头结点 int c = 0;while (entry.next != null && c < index) {entry = entry.next;c++;}return entry;}private void checkIndexBounds(int index) {if (index < 0 || index >= size)throw new IndexOutOfBoundsException("[index: " + index + ", size: "+ size + "]");} //结点对象 private static class Entry<T> {T element;Entry<T> next;public Entry(T element) {this(element, null);}public Entry(T element, Entry<T> next) {this.element = element;this.next = next;}}}public class LinkedList<T> {private Entry<T> head, tail;private int size;public LinkedList() {head = tail = null;size = 0;}public int size() {return size;}public boolean isEmpty() {return head == null; //头指针为空，表示整个链表为空}public T get(int index) {return current(index).element;}public T set(int index, T element) {Entry<T> entry = current(index);T oldVal = entry.element;entry.element = element;return oldVal;}public boolean add(T element) {Entry<T> newEntry = new Entry<T>(element);if (head == null) //如果头指针为空，直接将新结点赋值给头指针和尾指针head = tail = newEntry;else {tail.next = newEntry; //否则，尾指针的next指向新的结点，尾指针后移一位，指向新的结点tail = newEntry;}size++;return true;}public boolean add(int index, T element) { //若索引值和链表长度一样，新结点添加到链表最后位置 if (index == size)return add(element); //获得索引值为index-1的结点Entry<T> preEntry = previous(index);Entry<T> newEntry = new Entry<T>(element);if (preEntry == null) { //index=0 直接操作头指针newEntry.next = head;head = newEntry;} else { //其他情况，用获得的前一个结点完成添加操作newEntry.next = preEntry.next;preEntry.next = newEntry;}size++;return true;}public T remove(int index) { //获得索引值为index-1的结点Entry<T> preEntry = previous(index);T oldVal;if (preEntry == null) {//index=0 直接操作头指针oldVal = head.element;head = head.next;} else { //其他情况，用获得的前一个结点完成移除操作oldVal = preEntry.next.element; //如果preEntry的next刚好是最后一个结点，修改tail为preEntry if (tail == preEntry.next)tail = preEntry;preEntry.next = preEntry.next.next;}size--;return oldVal;}public void clear() {head = tail = null;size = 0;}public String toString() {String result = "[";Entry<T> entry = head;while (entry != null) {result += entry.element;entry = entry.next;if (entry != null)result += ", ";}return result + "]";}public Entry<T> current(int index) {checkIndexBounds(index);Entry<T> entry = head;int c = 0;while (entry != null && c < index) {entry = entry.next;c++;}return entry;}public Entry<T> previous(int index) {checkIndexBounds(index);if (index == 0) //索引为0 直接返回null，表明直接用头指针完成操作即可return null;Entry<T> entry = head;int c = 0;while (entry.next != null && c < index - 1) {entry = entry.next;c++;}return entry;}private void checkIndexBounds(int index) {if (index < 0 || index >= size)throw new IndexOutOfBoundsException("[index: " + index + ", size: "+ size + "]");}private static class Entry<T> {T element;Entry<T> next;public Entry(T element) {this(element, null);}public Entry(T element, Entry<T> next) {this.element = element;this.next = next;}}}