数据结构和算法:线性表链式存储的简单实现

一、先定义简单的线性表规则，然后实现

1、接口

/*** [Project]:moy-gradle-project <br/>* [Email]:moy25@ <br/>* [Date]:/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();}

View Code

2、实现

package com.moy.data.structure.list;/*** [Project]:moy-gradle-project <br/>* [Email]:moy25@ <br/>* [Date]:/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@ <br/>* [Date]:/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();}}

View Code

4、总结

a、实现简单的链式线性表来加深印象，使用链式存储的好处是不用担心扩容问题、新增和删除操作也不用进行数组位移，但是查找元素还是要遍历所有元素

b、查看官方实现java.util.LinkedList可知，其实现使用双向节点，在查询也做了优化，根据元素位置和链表总个数，决定从头节点还是尾节点开始查询

yexiangyang

moyyexy@