【数据结构】【线性表】链表

链表是一种链式存储的线性表，所有元素的内存地址不一定是连续的。

/**
* @Description: 线性表接口
* @Auther: zhurongsheng
* @Date: 2020/4/22 23:26
*/
public interface ZrsList<E> {
/**
* 元素数量
*/
int size();
/**
* 是否为空
*/
boolean isEmpty();
/**
* 是否包含
*/
boolean contains(E element);
/**
* 添加元素
*/
void add(E element);
/**
* 返回index位置对应的元素
*/
E get(int index);
/**
* 设置index位置的元素，返回原来的元素
*/
E set(int index, E element);
/**
* 在index位置添加元素
*/
void add(int index, E element);
/**
* 删除index对应的元素
*/
E remove(int index);
/**
* 查看元素的位置
*/
int indexOf(E element);
/**
* 清除所有元素
*/
void clear();
}

3 实现类

/**
* @Description:
* @Auther: zhurongsheng
* @Date: 2020/4/25 13:55
*/
public class ZrsLinkedList<E> implements ZrsList<E> {
private int size;
private Node<E> first;
private Node<E> last;
public ZrsLinkedList() {
}
@Override
public int size() {
return size;
}
@Override
public boolean isEmpty() {
return size == 0;
}
@Override
public boolean contains(E element) {
return false;
}
@Override
public void add(E element) {
Node<E> lastNode = last;
Node<E> newNode = new Node<>(element, null, lastNode);
last = newNode;
if (first == null)
first = newNode;
else
lastNode.next = newNode;
size++;
}
@Override
public E get(int index) {
rangeCheck(index);
return node(index).element;
}
private void rangeCheck(int index) {
if (index >= 0 && index <= size - 1) {
return;
}
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
private void rangeCheckForAdd(int index) {
if (index >= 0 && index <= size) {
return;
}
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
private String outOfBoundsMsg(int index) {
return "Index: " + index + ", Size: " + size;
}
@Override
public E set(int index, E element) {
rangeCheck(index);
Node<E> node = node(index);
E oldValue = node.element;
node.element = element;
return oldValue;
}
@Override
public void add(int index, E element) {
rangeCheckForAdd(index);
if (index == size) {
add(element);
} else {
Node<E> node = node(index);
Node<E> prevNode = node.prev;
Node<E> newNode = new Node<>(element, node, prevNode);
prevNode.next = newNode;
node.prev = newNode;
size++;
}
}
@Override
public E remove(int index) {
rangeCheck(index);
Node<E> node = node(index);
E oldVal = node.element;
Node<E> nextNode = node.next;
Node<E> prevNode = node.prev;
if (prevNode == null) {
first = nextNode;
} else {
prevNode.next = nextNode;
node.prev = null;
}
if (nextNode == null) {
last = prevNode;
} else {
nextNode.prev = prevNode;
node.next = null;
}
node.element = null;
size--;
return oldVal;
}
@Override
public int
indexOf(E element) {
int index = 0;
if (element == null) {
for (Node<E> node = first; node != null; node = node.next) {
if (node.element == null) return index;
index++;
}
} else {
for (Node<E> node = first; node != null; node = node.next) {
if (node.element.equals(element)) return index;
index++;
}
}
return -1;
}
private Node<E> node(int index) {
if (index < size / 2) {
Node<E> x = first;
for (int i = 0; i < index; i++) {
x = x.next;
}
return x;
} else {
Node<E> x = last;
for (int i = size - 1; i > index; i--) {
x = x.prev;
}
return x;
}
}
@Override
public void clear() {
for (Node<E> node = first; node != null; ) {
Node<E> next = node.next;
node.element = null;
node.next = null;
node.prev = null;
node = next;
}
first = null;
last = null;
size = 0;
}
private static class Node<E> {
private E element;
Node<E> next;
Node<E> prev;
private Node(E element, Node<E> next, Node<E> prev) {
this.element = element;
this.next = next;
this.prev = prev;
}
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
sb.append("[");
int index = 0;
for (Node<E> node = first; node != null; node = node.next) {
if (index == 0) {
sb.append(node.element);
} else {
sb.append(", ").append(node.element);
}
index++;
}
sb.append("]");
return sb.toString();
}
}

4 测试

/**
* @Description:
* @Auther: zhurongsheng
* @Date: 2020/4/25 15:05
*/
public class ListTest {
public static void main(String[] args) {
testZrsList();
System.out.println("################");
testJdkList();
}
private static void testJdkList() {
List<Integer> list = new LinkedList<>();
for (int i = 0; i < 10; i++) {
list.add(i,i);
}
list.add(5,50);
System.out.println(list.toString());
list.remove(5);
System.out.println(list.toString());
list.remove(0);
System.out.println(list.toString());
list.remove(list.size()-1);
System.out.println(list.toString());
}
private static void testZrsList(){
ZrsLinkedList<Integer> zrsList = new ZrsLinkedList<>();
for (int i = 0; i < 10; i++) {
zrsList.add(i,i);
}
zrsList.add(5,50);
System.out.println(zrsList.toString());
zrsList.remove(5);
System.out.println(zrsList.toString());
zrsList.remove(0);
System.out.println(zrsList.toString());
zrsList.remove(zrsList.size()-1);
System.out.println(zrsList.toString());
}
}

5 结果