上一篇博客中,博主和同学们一起认识了本系列中的第一个数据结构——线性表。在提供了抽象数据类型(ADT List)和Java版的MyList之后,我们又基于Java语言实现了在内存中顺序存储的线性表(也称为顺序表)。

    尽管我们在遇到频繁访问列表中元素时,ArrayList是一个很好的选择;但当我们需要频繁添加、删除列表中元素,尤其是在表的前端进行增删操作时,ArrayList就不是一个特别好的选择了。

    为了解决添加、删除元素时需要大量其它元素移动的问题,我们今天一起来接触在内存中链式存储的线性表(也称为链表)。

    链式存储的线性表同样需要一组存储单元去存储数据元素,但是这组存储单元可以是内存上连续的,也可以是内存上不连续的

    对于顺序存储的线性表来说,每个存储单元只需要存储数据元素即可,因为它们在内存上是连续的,第一个数据元素所占的内存空间之后,一定是下一个数据元素。

    但是对于链式存储的线性表来说,除了要存数据元素之外,还需要存它的后继元素的存储地址,因为下一个数据元素很可能在内存中任意位置。

    因此,对于每一个数据元素ai来说,除了存储其本身的数据信息之外,还需要存储一个指示其直接后继元素的内存位置。我们把存储数据元素信息的域称为数据域,把存储直接后继元素位置的域称为指针域。这两部分信息组成数据元素ai的存储映像,称为节点(Node)。n个节点连接成一个链表(a1,a2, … ,an),因为这个链表的每个节点中只包含一个指针域(指向它的直接后继元素),所以这种链表也成为单链表。

    • 下面我们就来一起用Java实现一个单链表MySinglyLinkedList
    	public class MySinglyLinkedList<E> implements MyList<E> {
    	
    	//单链表中的首节点,此节点不存放元素,只用来指向单链表中的第一个节点
    	private Node firstNode;
    	//单链表的元素数量
    	private int size;
    	
    	public MySinglyLinkedList() {
    		firstNode = new Node(null, null);
    		this.size = 0;
    	}
    	//内部类Node,用来表示单链表中每一个数据元素
    	class Node{
    		//数据域
    		E data;
    		//后继指针域,指向下一个数据元素
    		Node nextNode;
    		//提供一个构造函数
    		Node(E data, Node nextNode){
    			this.data = data;
    			this.nextNode = nextNode;
    		}
    	}
    
    • 接下来我们实现获取元素个数和查看是否为空的方法,很简单单行代码即可实现
    	@Override
    	public int size() {
    		// TODO Auto-generated method stub
    		return this.size;
    	}
    
    	@Override
    	public boolean isEmpty() {
    		// TODO Auto-generated method stub
    		return size()==0;
    	}
    
    • 然后是两种不同的插入方法
    	@Override
    	public boolean add(E e) {
    		// TODO Auto-generated method stub
    		//在单链表的结尾插入一个元素,就相当于在index为size的位置处插入元素
    		add(size(),e);
    		return true;
    	}
    
    	@Override
    	public void add(int index, E element) {
    		// TODO Auto-generated method stub
    		//一旦要插入元素的位置为负或大于目前的元素数量就抛出异常
                    //此处允许index等于size,相当于在单链表末尾插入元素
    		if(index<0 || index>size())
    			throw new IndexOutOfBoundsException();
    		//需要插入的元素
    		Node newNode = new Node(element, null);
    		//由于单链表只能从前往后遍历,因此要想在某个位置插入元素,必须先获得它前一个位置上的元素节点
    		//私有方法getPrevNodeByIndex可以用来获取该元素节点
    		Node posNode = getPrevNodeByIndex(index);
    		//需要被插入元素的后继元素指向索引位置的原节点
    		newNode.nextNode = posNode.nextNode;
    		//前一个位置的节点的后继元素指向被插入的节点
    		posNode.nextNode = newNode;
    		this.size++;
    	}
    	//私有方法getPrevNodeByIndex获取index前一个位置的节点
    	private Node getPrevNodeByIndex(int index) {
    		Node posNode = firstNode;
    		for(int i=0; i<index;i++) {
    			posNode = posNode.nextNode;
    		}
    		return posNode;
    	}
    
    • 紧接着是两个不同的删除方法
    	@Override
    	public boolean remove(Object o) {
    		// TODO Auto-generated method stub
    		if(isEmpty())
    			return false;
    		//如果需要被删除的元素为null
    		if(o == null) {
    			for(Node n = firstNode; n.nextNode!=null; n = n.nextNode) {
    				if(n.nextNode.data == null) {
    					Node targetNode = n.nextNode;
    					n.nextNode = targetNode.nextNode;
    					//让被删除节点的数据域,指针域和它的引用变量都指向null,方便GC工作
    					targetNode.data = null;
    					targetNode.nextNode = null;
    					targetNode = null;
    					this.size--;
    					return true;
    				}
    			}
    			return false;
    		}else {
    			for(Node n = firstNode; n.nextNode!=null; n = n.nextNode) {
    				if(o.equals(n.nextNode.data)) {
    					Node targetNode = n.nextNode;
    					n.nextNode = targetNode.nextNode;
    					//让被删除节点的数据域,指针域和它的引用变量都指向null,方便GC工作
    					targetNode.data = null;
    					targetNode.nextNode = null;
    					targetNode = null;
    					this.size--;
    					return true;
    				}
    			}
    			return false;
    		}
    	}
    
    	@Override
    	public E remove(int index) {
    		// TODO Auto-generated method stub
    		//一旦要插入元素的位置为负或大于目前的元素数量就抛出异常
                    //此处不允许index等于size
    		checkIndexValidation(index);
    		//获取要被删除节点的前驱节点
    		Node prevNode = getPrevNodeByIndex(index);
    		//获取要被删除的节点
    		Node targetNode = prevNode.nextNode;
    		//取出要被删除节点的数据域
    		E data = targetNode.data;
    		//要被删除节点的前驱节点的后继节点指向要被删除节点的后继节点
    		prevNode.nextNode = targetNode.nextNode;
    		//让被删除节点的数据域,指针域和它的引用变量都指向null,方便GC工作
    		targetNode.data = null;
    		targetNode.nextNode = null;
    		targetNode = null;
    		this.size--;
    		return data;
    	}
    
    • 之后是获取,修改,查看是否包含,以及清空整个列表这几个简单的方法了:
    	@Override
    	public E get(int index) {
    		// TODO Auto-generated method stub
    		checkIndexValidation(index);
    		return getPrevNodeByIndex(index).nextNode.data;
    	}
    
    	@Override
    	public E set(int index, E element) {
    		// TODO Auto-generated method stub
    		checkIndexValidation(index);
    		Node targetNode = getPrevNodeByIndex(index).nextNode;
    		E oldData = targetNode.data;
    		targetNode.data = element;
    		return oldData;
    	}
    	@Override
    	public boolean contains(Object o) {
    		// TODO Auto-generated method stub
    		if(isEmpty())
    			return false;
    		if(o == null) {
    			for(Node n = firstNode; n.nextNode!=null; n = n.nextNode) {
    				if(n.nextNode.data == null) {
    					return true;
    				}
    			}
    			return false;
    		}else {
    			for(Node n = firstNode; n.nextNode!=null; n = n.nextNode) {
    				if(o.equals(n.nextNode.data)) {
    					return true;
    				}
    			}
    			return false;
    		}
    	}
    	@Override
    	public void clear() {
    		// TODO Auto-generated method stub
    		for(Node n = firstNode.nextNode; n !=null;) {
    			Node next = n.nextNode;
    			n.data = null;
    			n.nextNode = null;
    			n = next;
    		}
    		firstNode.nextNode = null;
    		this.size = 0;
    	}
    

    我们在这里也分析一下MyLinkedList的特点:

    我们要读取或修改某一个位置的节点需要花费线性时间 O(n)去遍历列表;
    我们要增加或删除某一个(已知位置的)节点最坏情况下要花费常数时间 O(1)

    因此,当我们在遇到频繁访问列表中元素时,ArrayList是一个很好的选择;但当我们需要频繁在已知位置添加、删除列表中元素时,LinkedList有更好的性能。