×
文章路径: Java > 数据结构

链表java实现

发表于3年前(Dec 24, 2014 10:26:19 AM)  阅读 716  评论 0

分类: Java 数据结构

标签: LinkedList LinkList 双向链表 链表

链表是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点(链表中每一个元素称为结点)组成,结点可以在运行时动态生成。每个结点包括两个部分:一个是存储数据元素的数据域,另一个是存储下一个结点地址的指针域。 相比于线性表顺序结构,链表比较方便插入和删除操作。—-摘自百度百科。

只包含下一个节点的指针,这样的链表叫单向链表,如果还包含上一个链表的指针叫双向链表。在双向链表里,如果一个节点的上一个节点地址为空,则表示该节点为第一个节点,如果下一个节点的地址为空,则表示该接点为最后一个节点,如果两个都为空,表示该链表只有一个元素(数据不为空)或链表为空(数据为空)。 如果最后一个节点的下一个节点地址为第一个节点,这样的链表叫循环链表。

下面是双向不循环链表的java实现:

package cangzhitao.com.algorithms.datastructure;

/**
 * 双向链表
 * @author lihui
 *
 * @param <T>
 */
@SuppressWarnings("unchecked")
public class LinkList<T> {

	private Node<T> list;

	public LinkList() {
		super();
		list = new Node<T>();
		list.pre = null;
		list.next = null;
	}

	/**
	 * 链表是否为空
	 * @return
	 */
	public boolean isEmpty() {
		if(list.data==null) {
			return true;
		} else {
			return false;
		}
	}

	/**
	 * 获得链表第一个元素
	 * @return
	 */
	public Node<T> first() {
		if(isEmpty()) {
			return null;
		} else {
			return list;
		}
	}

	/**
	 * 获得链表最后一个元素
	 * @return
	 */
	public Node<T> last() {
		if(isEmpty()) {
			return null;
		} else {
			Node<T> node = list;
			while(node.next!=null) {
				node = node.next;
			}
			return node;
		}
	}

	/**
	 * 返回链表中第index个元素
	 * @param index
	 * @return
	 */
	public Node<T> indexOf(int index) {
		if(index<0) {
			return null;
		}
		if(isEmpty()) {
			return null;
		} else {
			Node<T> node = list;
			while(true) {
				if(index==0) {
					return node;
				} else {
					if(node.next==null) {
						return null;
					} else {
						index--;
						node = node.next;
					}
				}
			}
		}
	}

	/**
	 * 插入data元素到最后一个元素后面
	 * @param data
	 * @return
	 */
	public LinkList<T> insert(T data) {
		Node<T> node = new Node(data);
		if(isEmpty()) {
			list = node;
		} else {
			Node<T> last = last();
			last.next = node;
			node.pre = last;
		}
		return this;
	}

	/**
	 * 将元素data插入指定位置,如果index<0插在最前面,如果index超出了索引界限,则插到最后面
	 * @param data
	 * @param index
	 * @return
	 */
	public LinkList<T> insert(T data, int index) {
		if(index<0) {
			index = 0;
		}
		if(isEmpty()) {
			list.data = data;
			return this;
		}
		Node<T> node = new Node(data);
		Node<T> next = indexOf(index);
		Node<T> pre = null;
		//超出索引界限,插在最后一个位置
		if(next==null) {
			next = last();
			node.pre = next;
			next.next = node;
		} else {
			pre = next.pre;
			//插在第一个元素
			if(pre==null) {
				next.pre = node;
				node.next = next;
			//插在pre跟next中间
			} else {
				pre.next = node;
				node.pre = pre;

				next.pre = node;
				node.next = next;
			}

		}
		return this;
	}

	/**
	 * 寻找链表中第一个数据等于data的索引
	 * @param data
	 * @return
	 */
	public int search(T data) {
		int index = -1;
		T value = list.data;
		while(true) {
			index ++;
			//找到目标元素
			if(data.equals(value)) {
				return index;
			//最后一个元素也不是目标元素
			} else if(list.next==null) {
				return -1;
			//继续搜索
			} else {
				value = list.next.data;
			}
		}
	}

	/**
	 * 返回链表长度
	 * @return
	 */
	public int size() {
		if(isEmpty()) {
			return 0;
		}
		int n = 1;
		Node<T> node = list;
		while((node=node.next)!=null) {
			n++;
		}
		return n;
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		LinkList<Integer> list = new LinkList<Integer>();
		System.out.println(list.size());
		list.insert(1);
		list.insert(2);
		list.insert(3);
		System.out.println(list.size());
		System.out.println(list.indexOf(2));
		System.out.println(list.indexOf(3));

	}

}
链表中的节点类实现:

package cangzhitao.com.algorithms.datastructure;

/**
 * 链表中的节点类
 * @author lihui
 * @param <T>
 */
public class Node<T> {

	/**
	 * 指向前一个节点
	 */
	public Node<T> pre = null;

	/**
	 * 指向后一个节点
	 */
	public Node<T> next = null;

	/**
	 * 数据项
	 */
	public T data;

	public Node() {

	}

	public Node(T data) {
		super();
		this.data = data;
	}

	public String toString() {
		return data.toString();
	}

}

发表评论