链表的设计
接口设计
链表的大部分接口和动态数组是一致的 清空元素-clear()@Override
public void clear() {
size=0;
first=null;
}
AbstractList.java
public abstract class AbstractList<E> implements List<E> {
/**
* 元素的数量
*/
protected int size;
/**
* 元素的数量
* @return
*/
public int size() {
return size;
}
/**
* 是否为空
* @return
*/
public boolean isEmpty() {
return size == 0;
}
/**
* 是否包含某个元素
* @param element
* @return
*/
public boolean contains(E element) {
return indexOf(element) != ELEMENT_NOT_FOUND;
}
/**
* 添加元素到尾部
* @param element
*/
public void add(E element) {
add(size, element);
}
protected void outOfBounds(int index) {
throw new IndexOutOfBoundsException("Index:" + index + ", Size:" + size);
}
protected void rangeCheck(int index) {
if (index < 0 || index >= size) {
outOfBounds(index);
}
}
protected void rangeCheckForAdd(int index) {
if (index < 0 || index > size) {
outOfBounds(index);
}
}
}
LinkedList.java
public class LinkedList<E> extends AbstractList<E>{
private Node<E> first;
private static class Node<E> {
E element;
Node<E> next;
public Node(E element,Node<E> next) {
this.element=element;
this.next=next;
}
}
@Override
public void clear() {
size=0;
first=null;
}
@Override
public boolean contains(E element) {
return indexOf(element)!=ELEMENT_NOT_FOUND;
}
@Override
public E get(int index) {
return node(index).element;
}
@Override
public E set(int index, E element) {
Node<E> node = node(index);
E old=node.element;
node.element=element;
return old;
}
@Override
public void add(int index, E element) {
rangeCheckForAdd(index);
if(index==0) {
first=new Node<>(element,first);
}else {
Node<E> prev = node(index - 1);
prev.next = new Node<>(element, prev.next);
}
size++;
}
@Override
public E remove(int index) {
rangeCheck(index);
Node<E> node=first;
if(index==0){
first=first.next;
}else {
Node<E> prev = node(index - 1);
node=prev.next;
prev.next = prev.next.next;
}
size--;
return node.element;
}
@Override
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;
}
/**
* 获取index位置对应的节点对象
* @param index
* @return
*/
private Node<E> node(int index){
rangeCheck(index);
Node<E> node = first;
for(int i=0;i<index;i++){
node=node.next;
}
return node;
}
@Override
public String toString() {
StringBuilder string = new StringBuilder();
string.append("size=").append(size).append(",[");
Node<E> node = first;
for(int i=0;i<size;i++){
if(i!=0){
string.append(",");
}
string.append(node.element);
node=node.next;
}
string.append("]");
return string.toString();
}
}
有时候为了让代码更加精简，统一所有节点的处理逻辑，可以在最前面增加一个虚拟的头节点（不存储数据）
动态数组、链表复杂度分析
双向链表使用双向链表可以提升链表的综合性能
private Node<E> first;
private Node<E> last;
private static class Node<E> {
E element;
Node<E> prev;
Node<E> next;
public Node(Node<E> prev,E element,Node<E> next) {
this.prev=prev;
this.element=element;
this.next=next;
}
}
clear()
@Override
public void clear() {
size=0;
first=null;
last=null;
}
add()
public void add(int index, E element) {
rangeCheckForAdd(index);
if(index==size){
Node<E> oldLast = last;
last = new Node<>(oldLast,element,null);
if(oldLast==null){
first=last;
}else {
oldLast.next=last;
}
}else{
Node<E> next = node(index);
Node<E> prev = next.prev;
Node<E> node = new Node<>(prev, element, next);
next.prev = node;
if (prev == null) {
first = next;
} else {
prev.next = next;
}
}
size++;
}
动态数组：开辟、销毁内存空间的次数相对较少，但可能造成内存空间浪费（可通过缩容解决）
双向链表：开辟、销毁内存空间的次数相对较多，但不会造成内存空间的浪费
如果频繁在尾部进行添加、删除 *** 作，动态数组、双向链表均可选择
如果频繁在头部进行添加、删除 *** 作，建议选择使用双向链表
如果有频繁的（在任意位置）添加、删除 *** 作，建议选择使用双向链表
如果有频繁的 *** 作 *** 作（随机访问 *** 作），建议选择使用动态数组
单向循环链表add()
@Override
public void add(int index, E element) {
rangeCheckForAdd(index);
if(index==0) {
Node<E> newfirst=new Node<>(element,first);
//拿到最后一个节点
Node<E> last = (size==0) ? newfirst : node(size-1);
last.next=newfirst;
first=newfirst;
}else {
Node<E> prev = node(index - 1);
prev.next = new Node<>(element, prev.next);
}
size++;
}
remove()
@Override
public E remove(int index) {
rangeCheck(index);
Node<E> node=first;
if(index==0){
if(size==1){
first=null;
}else {
Node<E> last = node(size-1);
first=first.next;
last.next=first;
}
}else {
Node<E> prev = node(index - 1);
node=prev.next;
prev.next = prev.next.next;
}
size--;
return node.element;
}
add()
@Override
public void add(int index, E element) {
rangeCheckForAdd(index);
if(index==size){
Node<E> oldLast = last;
last = new Node<>(oldLast,element,first);
if(oldLast==null){
first=last;
first.next=first;
first.prev=first;
}else {
oldLast.next=last;
first.prev=last;
}
}else{
Node<E> next = node(index);
Node<E> prev = next.prev;
Node<E> node = new Node<>(prev, element, next);
next.prev = node;
prev.next = node;
if (index==0) {
first = next;
}
}
size++;
}
remove()
@Override
public E remove(int index) {
rangeCheck(index);
Node<E> node=first;
if(size==1){
first=null;
last=null;
}else {
node = node(index);
Node<E> prev = node.prev;
Node<E> next = node.next;
prev.next = next;
next.prev = prev;
if (node == first) {
first = next;
}
if (node == last) {
last = prev;
}
}
size--;
return node.element;
}
如何发挥循环链表的最大威力
可以考虑增设1个成员变量、3个方法
current：用于指向某个节点
void reset()：让current指向头节点first
E next()：让current往后走一步，也就是current=current.next
E remove()：删除current指向的节点，删除成功后让current指向下一个节点
@Override
public E remove(int index) {
rangeCheck(index);
return remove(node(index));
}
public E remove(){
if(current==null)return null;
Node<E> next = current.next;
E element = remove(current);
if(size==0){
current=null;
}else{
current=next;
}
return element;
}
private E remove(Node<E> node){
if(size==1){
first=null;
last=null;
}else {
Node<E> prev = node.prev;
Node<E> next = node.next;
prev.next = next;
next.prev = prev;
if (node == first) {
first = next;
}
if (node == last) {
last = prev;
}
}
size--;
return node.element;
}
public void reset(){
current=first;
}
public E next(){
if(current==null)return null;
current=current.next;
return current.element;
}
用数组模拟链表，称为静态链表
数组的每个元素存放2个数据：值、下个元素的索引
数据0位置存放的是头节点信息
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）