单向链表的实现(java)

1. 结构定义：

public class LinkedList<E> { private int size; private Node<E> first; static final int ELEMENT_NOT_FOUND = -1; private static class Node<E> { E element; Node<E> next; public Node(E element, Node<E> next) { this.element = element; this.next = next; } /** * 清除所有元素 */ public void clear(); /** * 元素的数量 * @return */ public int size(); /** * 是否为空 * @return */ public boolean isEmpty(); /** * 是否包含某个元素 * @param element * @return */ public boolean contains(E element); /** * 查看元素的索引 * @param element * @return */ public int indexOf(E element); /** * 获取index位置对应的节点对象 * @param index * @return */ private Node<E> node(int index); /** * 添加元素到尾部 * @param element */ public void add(E element); /** * 获取index位置的元素 * @param index * @return */ public E get(int index); /** * 设置index位置的元素 * @param index * @param element * @return 原来的元素ֵ */ public E set(int index, E element); /** * 在index位置插入一个元素 * @param index * @param element */ public void add(int index, E element); /** * 删除index位置的元素 * @param index * @return */ public E remove(int index); }

2. 清空元素

public void clear(){ size = 0; first = null; }

3. 获取元素个数

public int size(){ return size; }

4.是否为空

public boolean isEmpty(){ return size == 0; }

5.查看元素的索引

public int indexOf(E element){ if(element == null){ Node<E> node = first; for(int i = 0; i < size; i++){ if(node.element == null) return i; node = node.next; } } else{ Node<E> node = first; for(int i = 0; i < size; i++){ if(element.equals(node.element)) return i; node = node.next; } } return ELEMENT_NOT_FOUND; }

6.是否包含某个元素

public boolean contains(E element){ return indexOf(element) != ELEMENT_NOT_FOUND; }

7.获取index位置对应的节点对象

private Node<E> node(int index){ if (index < 0 || index >= size) { throw new IndexOutOfBoundsException("Index:" + index + ", Size:" + size); } Node<E> node = first; for(int i = 0; i < index; i++ ){ node = node.next; } return node; }

8.获取index位置的元素

public E get(int index){ return node(index).element; }

9.设置index位置的元素

public E set(int index, E element){ Node<E> node = node(index); E old = node.element; node.element = element; return old; }

10.在index位置插入一个元素

public void add(int index, E element){ if (index < 0 || index > size) { throw new IndexOutOfBoundsException("Index:" + index + ", Size:" + size); } if(index == 0){ first = new Node<E>(element, first); }else{ Node<E> prev = node(index-1); prev.next = new Node<E>(element, prev.next); } size++; }

11.添加元素到尾部

public void add(E element){ add(size,element); }

12.删除index位置的元素

public E remove(int index){ if (index < 0 || index >= size) { throw new IndexOutOfBoundsException("Index:" + index + ", Size:" + size); } Node<E> node = first; if(index == 0){ first = first.next; } else{ Node<E> prev = node(index-1); node = prev.next; prev.next = node.next; } size--; return node.element; }