java单链表-牵头结点和不带头结点单链表的简单实现
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; } } }