一、先定義簡單的線性表規則，然后實現
1、接口
/*** [Project]:moy-gradle-project <br/>* [Email]:moy25@foxmail.com <br/>* [Date]:2018/1/24 <br/>* [Description]: 簡單的線性表定義<br/>** @author YeXiangYang*/ public interface SimpleList<E> {/*** 添加元素** @param e 需要添加的元素* @return 添加成功返回<tt>true<tt/>*/boolean add(E e);/*** 將元素添加到指定下標上，對應下標不存在拋出異常** @param index 下標* @param e 元素* @return 添加成功返回<tt>true<tt/>*/boolean add(int index, E e);/*** 刪除最后一個元素，集合為空則拋出異常** @return 被刪除的元素*/E removeLast();/*** 刪除指定下標的元素，對應下標不存在拋出異常** @param index* @return 被刪除的元素*/E remove(int index);/*** 刪除集合中的對于元素** @param e 需要被刪除的元素* @return 刪除成功返回<tt>true<tt/>*/boolean remove(E e);/*** 將指定下標改成對應元素，對應下標不存在拋出異常** @param index 下標* @param e 需要添加到指定位置為元素* @return*/E set(int index, E e);/*** 獲取指定下標的元素，對應下標不存在拋出異常** @param index 下標* @return 下標對應的元素*/E get(int index);/*** 返回元素對應的最小下標** @param e 元素* @return 返回元素對應的最小下標，不存在返回<tt>-1<tt/>*/int indexOf(E e);/*** 判斷集合中是否包含目標元素** @param o 目標元素* @return 該集合存在目標元素，返回<tt>true<tt/>*/boolean contains(Object o);/*** 獲取集合元素個數** @return 集合中元素個數*/int size();/*** 判斷集合中是否為空** @return 集合中為空返回<tt>true<tt/>*/boolean isEmpty();/*** 清除集合中所有元素*/void clear();/*** 重寫toString方法** @return 返回友好信息*/String toString(); }
2、實現
package com.moy.data.structure.list;/*** [Project]:moy-gradle-project <br/>* [Email]:moy25@foxmail.com <br/>* [Date]:2018/1/27 <br/>* [Description]: <br/>** @author YeXiangYang*/ public class SimpleLinkedList<E> implements SimpleList<E> {private int size;private transient Node<E> first;private transient Node<E> last;@Overridepublic boolean add(E e) {return add(size, e);}@Overridepublic boolean add(int index, E e) {if (index < 0 || index > size) {throw new IllegalArgumentException("index:" + index + ",size:" + size);}if (null != first) {if (0 == index) {Node<E> newData = new Node<>(e, first);first = newData;} else if (size == index) {Node<E> newData = new Node<>(e, null);last.next = newData;last = newData;} else {Node<E> prevNode = getNode(index - 1);Node<E> oldNode = prevNode.next;Node<E> newData = new Node<>(e, oldNode);prevNode.next = newData;}} else {Node<E> newData = new Node<>(e, null);this.first = newData;this.last = newData;}size++;return Boolean.TRUE;}@Overridepublic E removeLast() {return remove(size - 1);}@Overridepublic E remove(int index) {rangeCheck(index);E oldData = null;if (0 == index) {oldData = first.data;first.data = null;first = first.next;} else if (size - 1 == index) {Node<E> lastNode = getNode(index - 1);lastNode.next = null;oldData = last.data;last.data = null;last = lastNode;} else {Node<E> lastNode = getNode(index - 1);Node<E> currentNode = lastNode.next;Node<E> nextNode = currentNode.next;lastNode.next = nextNode;oldData = currentNode.data;currentNode.data = null;currentNode.next = null;}size--;return oldData;}@Overridepublic boolean remove(E e) {int targetIndex = indexOf(e);if (targetIndex >= 0) {remove(targetIndex);return Boolean.TRUE;}return Boolean.FALSE;}@Overridepublic E set(int index, E e) {Node<E> node = getNode(index);E oldData = node.data;node.data = e;return oldData;}@Overridepublic E get(int index) {Node<E> node = getNode(index);return node.data;}private Node<E> getNode(int index) {rangeCheck(index);Node<E> current = this.first;if (null != current) {int dataIndex = -1;while (null != current) {dataIndex++;if (dataIndex == index) {return current;}current = current.next;}}throw new IllegalArgumentException("index:" + index + ",size:" + size);}private void rangeCheck(int index) {if (index < 0 || index >= size) {throw new IllegalArgumentException("index:" + index + ",size:" + size);}}@Overridepublic int indexOf(E e) {if (null != first) {int index = -1;Node<E> current = this.first;do {index++;if (null == e) {if (null == current.data) {return index;}} else {if (e.equals(current.data)) {return index;}}current = current.next;} while (null != current);}return -1;}@Overridepublic int size() {return size;}@Overridepublic boolean isEmpty() {return 0 == size;}@Overridepublic boolean contains(Object o) {try {E e = (E) o;return indexOf(e) >= 0;} catch (Exception e) {// 轉型出錯則不包含 }return Boolean.FALSE;}@Overridepublic void clear() {if (null != first) {Node<E> currentNode = this.first;while (null != currentNode) {currentNode.data = null;currentNode = currentNode.next;}}first = null;last = null;size = 0;}private static class Node<E> {Node<E> next;E data;public Node(E data, Node<E> next) {this.next = next;this.data = data;}}public SimpleLinkedList() {first = null;last = null;size = 0;}@Overridepublic String toString() {if (null == first) {return "[]";}StringBuilder result = new StringBuilder();Node<E> currentNode = this.first;boolean isFirst = Boolean.TRUE;do {if (isFirst) {result.append("[");isFirst = Boolean.FALSE;} else {result.append(", ");}result.append(String.valueOf(currentNode.data));currentNode = currentNode.next;} while (null != currentNode);result.append("]");return result.toString();} }
線性表的鏈式存儲結構是一種。3、測試
package com.moy.data.structure;import com.moy.data.structure.list.SimpleLinkedList; import com.moy.data.structure.list.SimpleList; import org.junit.After; import org.junit.Before; import org.junit.Test;import java.util.LinkedList; import java.util.List;/*** [Project]:moy-gradle-project <br/>* [Email]:moy25@foxmail.com <br/>* [Date]:2018/1/28 <br/>* [Description]:* <p><br/>** @author YeXiangYang*/ public class SimpleLinkedListTest {SimpleList<Object> simpleList;List<Object> list;@Beforepublic void before() {int len = 10;simpleList = new SimpleLinkedList<>();list = new LinkedList<>();insertInitSimpleList(len);insertInitList(len);System.out.println("**************** Before ******************");System.out.println("自定義執行測試方法之前:\t" + simpleList);System.out.println("官方的執行測試方法之前:\t" + list);}private void insertInitList(int len) {for (int i = 0; i < len; i++) {if (len / 2 == i) {list.add(null);} else {list.add(i);}}}private void insertInitSimpleList(int len) {for (int i = 0; i < len; i++) {if (len / 2 == i) {simpleList.add(null);} else {simpleList.add(i);}}}@Afterpublic void after() {System.out.println("自定義執行測試方法之后:\t" + simpleList);System.out.println("官方的執行測試方法之后:\t" + list);System.out.println("**************** After *******************");System.out.println();}@Testpublic void addTest() {int index = 10;Object data = 123;try {System.out.println(simpleList.add(index, data));} catch (Exception e) {e.printStackTrace();}try {list.add(index, data);} catch (Exception e) {e.printStackTrace();}}@Testpublic void removeTest() {System.out.println(list.remove(list.size() - 1));System.out.println(simpleList.removeLast());Integer removeData = new Integer("7");System.out.println(list.remove(removeData));System.out.println(simpleList.remove(removeData));System.out.println(list.remove(null));System.out.println(simpleList.remove(null));}@Testpublic void setTest() {int index = 0;Object data = 2333;try {System.out.println(simpleList.set(index, data));} catch (Exception e) {e.printStackTrace();}try {System.out.println(list.set(index, data));} catch (Exception e) {e.printStackTrace();}}@Testpublic void getTest() {int index = 0;try {System.out.println(simpleList.get(index));} catch (Exception e) {e.printStackTrace();}try {System.out.println(list.get(index));} catch (Exception e) {e.printStackTrace();}}@Testpublic void isEmptyTest() {System.out.println(list.isEmpty());System.out.println(simpleList.isEmpty());}@Testpublic void containsTest() {Object object = 0;System.out.println(list.contains(object));System.out.println(simpleList.contains(object));}@Testpublic void clearTest() {list.clear();simpleList.clear();} }
4、總結
? ? ?a、實現簡單的鏈式線性表來加深印象，使用鏈式存儲的好處是不用擔心擴容問題、新增和刪除操作也不用進行數組位移，但是查找元素還是要遍歷所有元素
? ? ?b、查看官方實現java.util.LinkedList可知，其實現使用雙向節點，在查詢也做了優化，根據元素位置和鏈表總個數，決定從頭節點還是尾節點開始查詢
yexiangyang
moyyexy@gmail.com
?
