线性表的链式存储与实现

单向链表

单向链表 ,即单链表. 每个存储单元至少有两个存储域, 一个用来存储数据, 一个域保存下个存储单元的引用。

各个存储单元的地址可以是不连续的。

插入/删除时不需要移动元素

通过单向链表实现线性表

/**
 * 通过单向链表实现线性表
 * @author 北京乐学网老崔
 */

public class MySingleLink implements MyList {
	private Node head;			//头结点
	private int size; 			//保存元素的个数
	
	// 返回元素的个数
	@Override
	public int getSize() {
		return size;
	}

	// 判断线性表是否为空
	@Override
	public boolean isEmpty() {
		return size == 0 ;
	}

	// 在线性表中插入元素
	@Override
	public void insert(int i, Object e) {
		//判断索引值是否越界
		if ( i < 0 || i > size) {
			throw new IndexOutOfBoundsException(i+"越界");
		}
		//创建结点
		Node newNode = new Node(e, null);
		//头结点为null的情况,链表不存在, 刚刚添加的结点就是头结点
		if (head == null) {
			head = newNode; 
		}else {
			//在0位置插入结点
			if (i == 0 ) {
				newNode.next = head; 		//修改新结点的next域指向原来的头结点
				head = newNode;			//刚插入的结点就是新的头结点
			}else {
				//插入结点, 先找到i-1这个结点
				Node pNode = head; 
				for( int x = 1; x<i; x++) {
					pNode = pNode.next; 
				}
				//注意,先修改新结点的next指针域, 再修改i-1结点的指针域
				newNode.next = pNode.next;
				pNode.next = newNode;
			}
		
		}
		//元素个数加0
		size++;
	}

	// 判断线性表中是否包含指定的元素
	@Override
	public boolean contains(Object e) {
		return indexOf(e) >= 0 ;
	}

	// 返回元素e在线性表中第一次出现的索引值
	@Override
	public int indexOf(Object e) {
		int i  = 0  ;		//保存元素e的索引值
		Node pNode = head; 
		while( pNode != null) {
			if ( e == null && pNode.data == null) {
				return i;
			}else if (e != null && e.equals(pNode.data)) {
				return i;
			}
			i++;
			pNode = pNode.next;
		}
		return -1;
	}

	//从线性表中删除第一个与e相同的元素
	@Override
	public Object remove(Object e) {
		//找到元素e第一次出现的索引值
		int index = indexOf(e);
		if (index < 0 ) {
			return null; 		//元素不存在
		}
		return remove(index);
	}

	//从线性表中删除指定索引的元素
	@Override
	public Object remove(int i) {
		//判断是否越界
		if (i < 0 || i >= size) {
			throw new IndexOutOfBoundsException(i + "越界");
		}
		Node pNode = head;
		//删除头结点
		if (i == 0) {
			head = head.next;
			size--;
			return pNode.data; 		//返回删除头结点的数据
		}
		//找到i-1结点
		for( int x = 1; x < i ; x++) {
			pNode = pNode.next;
		}
		//
		Object old = pNode.next.data; 		//保存删除结点的数据
		pNode.next = pNode.next.next;		//修改i-1结点的next指针域 ,指向 i+1结点
		size--;
		
		return old;
	}

	// 把线性表中i索引值的元素替换 为e
	@Override
	public Object replace(int i, Object e) {
		//判断是否越界
		checkIndex(i);
		
		//找到i结点
		Node pNode = getNode(i);
		Object old = pNode.data ;		//保存原来的数据
		pNode.data = e;		//替换
		return old;
	}

	// 返回线性表中i索引值的元素
	@Override
	public Object get(int i) {
		checkIndex(i);
		Node pNode = getNode(i);
		return pNode.data;
	}
	//检查索引值是否越界
	private void checkIndex(int i ) {
		if (i < 0 || i >= size) {
			throw new IndexOutOfBoundsException(i + "越界");
		}
	}
	
	//定义一个方法,返回i索引值的元素
	private Node getNode(int i) {
		if ( i < 0 || i >= size) {
			return null;
		}
		if (i == 0) {
			return head;
		}
		//找到i结点
		Node pNode = head;
		for( int x = 1; x <= i ; x++) {
			pNode = pNode.next;
		}
		return pNode;
	}

	// 在指定的元素p的前面插入元素e
	@Override
	public boolean insertBefore(Object p, Object e) {
		//找p的位置
		int index = indexOf(p);
		if (index < 0 ) {
			return false; 		//元素p不存在
		}
		insert(index, e);
		return true;
	}
	// 在指定的元素p的后面插入元素e
	@Override
	public boolean insertAfter(Object p, Object e) {
		// 找p的位置
		int index = indexOf(p);
		if (index < 0) {
			return false; // 元素p不存在
		}
		insert(index+1, e);
		return true;
	}

	//重写toString()
	@Override
	public String toString() {
		// 把链表中各个结点的数据域连接起来
		StringBuilder sb = new StringBuilder();
		sb.append("[");
		Node pNode = head;
		while(pNode != null) {
			sb.append(pNode.data);
			//使用逗号分隔
			if (pNode.next != null) {
				sb.append(",");
			}
			pNode = pNode.next; 		//指针下移
		}
		sb.append("]");
		return sb.toString();
	}
	//定义一个内部类表示单向链表中的结点
	private class Node{
		Object data;		//保存数据
		Node next;			//下个结点的引用
		public Node(Object data, Node next) {
			super();
			this.data = data;
			this.next = next;
		}
		
		
	}
}

双向链表

单向链表只能通过一个结点的引用访问它的后续结点, 不能访问前驱结点, 如果要找某个 结点的前驱结点, 需要从头结点开始依次查找。

在双向链表中,扩展了结点的结构, 每个 结点除了存储数据外, 通过一个引用指向后续结点,再定义一个引用指向前驱结点：

双向链表的结构:

插入元素

双向链表实现线性表

/**
 * 双向链表
 * @author 北京乐学网老崔
 */
public class MyDualLinkedList implements MyList {
	private  Node first; 			//指向头结点
	private  Node last; 			//指向尾结点
	private int  size; 				//保存元素的个数
	
	// 返回元素的个数
	@Override
	public int getSize() {
		return size;
	}

	// 判断链表是否为空
	@Override
	public boolean isEmpty() {
		return size == 0 ;
	}

	// 在指定的索引值插入元素
	@Override
	public void insert(int i, Object e) {
		//1)检查索引值是否越界
		if (i < 0 || i > size) {
			throw  new IndexOutOfBoundsException(i + "越界");
		}
		//2) 如果i==0,  在头部添加元素
		if ( i == 0 ) {
			addFirst(e);
		}else if( i == size ) {
			//3) 如果i==size, 在尾部添加元素
			addLast(e);
		}else {
			//4) 找到i结点, 在i结点的前面插入元素
			Node pNode = getNode(i);
			Node prevNode = pNode.prev;
			//生成新的结点
			Node newNode = new Node(e, prevNode, pNode);
			//修改前驱结点的后续			
			prevNode.next = newNode;
			pNode.prev = newNode;
			size++;
		}
	}

	//返回索引值对应的结点
	private Node getNode(int i) {
		// 
		Node pNode = first;
		for( int x = 0 ; x < i; x++) {
			pNode = pNode.next;
		}
		return pNode;
	}

	

	// 判断链表 中是否包含指定的元素e, 如果存在返回true
	@Override
	public boolean contains(Object e) {
		return indexOf(e) >= 0;
	}

	// 判断元素e在链表中第一次出现的位置, 如果不存在该元素返回-1
	@Override
	public int indexOf(Object e) {
		int i = 0 ; 			//保存元素e在链表中的索引值
		//依次遍历链表中的各个结点, 比较结点的元素与指定的e是否一样
		if (e == null) {
			for( Node  pNode = first;  pNode != null ; pNode = pNode.next) {
				if ( pNode.data == null ) {
					return i;
				}
				i++;
			}
		}else {
			for( Node  pNode = first;  pNode != null ; pNode = pNode.next) {
				if ( e.equals(pNode.data) ) {
					return i;
				}
				i++;
			}
		}
		return -1;
	}

	// 从链表中删除指定的元素, 并返回删除的元素
	@Override
	public Object remove(Object e) {
		//找到元素e对应的索引值
		int index = indexOf(e);
		if ( index < 0 ) {
			return null; 			 
		}
		return remove(index);
	}

	// 从链表中删除指定索引值的元素, 并返回删除的元素
	@Override
	public Object remove(int i) {
		//判断索引值是否越界
		checkIndex(i);
		//找到i对应的结点
		Node pNode = getNode(i);
		Node prevNode = pNode.prev; 		//删除结点的前驱
		Node nextNode = pNode.next; 		//删除结点的后续
		
		if ( prevNode == null) {
			//删除的头结点
			first = nextNode;
		}else {
			prevNode.next = nextNode;
		}
		
		if ( nextNode == null) {
			//删除尾结点
			last = prevNode;
		}else {
			nextNode.prev = prevNode;
		}
		
		size--; 				//修改元素个数
		
		return pNode.data;
	}

	//检查索引值是否越界
	private void checkIndex(int i) {
		if ( i < 0 || i >= size ) {
			throw new IndexOutOfBoundsException(i + "越界");
		}
	}

	// 修改指定索引值的元素, 把原来的元素返回
	@Override
	public Object replace(int i, Object e) {
		//检查索引值是否越界
		checkIndex(i);
		
		//找到索引值为i的结点
		Node pNode = getNode(i);
		Object oldData = pNode.data;
		pNode.data = e; 	//修改结点的元素
		return oldData;
	}

	// 返回指定索引值的元素
	@Override
	public Object get(int i) {
		//检查索引值越界
		checkIndex(i);
		//找到索引值为i的结点
		Node pNode = getNode(i);
		return pNode.data;
	}

	// 在指定的元素p前面插入元素e
	@Override
	public boolean insertBefore(Object p, Object e) {
		//找到p元素在链表中的位置
		int index = indexOf(p);
		if (index < 0) { 			//链表中不存在元素p
			return false;
		}
		insert(index, e);  		//在p元素的前面插入元素e
		return true;
	}

	// 在指定的元素p后面插入元素e
	@Override
	public boolean insertAfter(Object p, Object e) {
		// 找到p元素在链表中的位置
		int index = indexOf(p);
		if (index < 0) { // 链表中不存在元素p
			return false;
		}
		insert(index + 1, e);  // 在p元素的后面插入元素e
		return true;
	}

	@Override
	public String toString() {
		// 依次遍历各个结点,把元素转换为字符串
		StringBuilder sb = new StringBuilder();
		sb.append("[");
		
		for( Node node = first ;  node != null ; node = node.next) {
			sb.append( node.data );
			//元素之间使用逗号分隔
			if ( node != last ) {
				sb.append(",");
			}
		}
		
		sb.append("]");
		return sb.toString();
	}
	
	//在链表中,经常会有针对头元素与尾元素的操作// 在链表的尾部添加元素
	public void addLast(Object e) {
		Node pNode = last;
		//生成一个新的结点
		Node newNode = new Node(e, last, null);
		if (pNode == null ) {
			first = newNode;
		}else {
			pNode.next = newNode;
		}
		last = newNode ;
		size++;
	}

	//在头部添加元素e
	public void addFirst(Object e) {
		Node pNode = first;    
		// 生成一个新的结点
		Node newNode = new Node(e, null, first);		
		first = newNode; 		//修改first指向新的结点
		if ( pNode == null ) {
			last = newNode;
		}else {
			pNode.prev = newNode;
		}
		size++; 		//元素的个数加1 
	}
	
	//删除第一个元素, 删除头元素
	public Object removeFirst() {
		return remove(0);
	}
	//删除最后一个元素(尾元素)
	public Object removeLast() {
		return remove(size-1);
	}
	//返回头元素
	public Object getFirst() {
		return get(0);
	}
	//返回最后一个元素
	public Object getLast() {
		return get(size-1);
	}
	

	//定义一个内部类描述双向链表的结点
	private class Node {
		Object data;
		Node prev;			//指向前驱结点
		Node next;			//指向后继结点
		public Node(Object data, Node prev, Node next) {
			super();
			this.data = data;
			this.prev = prev;
			this.next = next;
		}
	}
	
}