数据结构之链表

数据结构之链表

 

链表 不同于我们之前学的队列与数组，他的特殊在于结点与元素的联系，链表访问的实现在于结点选择，更要的是分清结点与结点连接的元素的关系。

 

双链表 实现链表的双向访问。

下面是双链表的简单实现

public class LinkNode {
private LinkNode parent;
private LinkNode child;
private Object obj;
	public LinkNode(Object obj) {
		this.obj = obj;
	}
	public Object getObject() {
		return obj;
	}
	
	
	public LinkNode getParent() {
		return parent;
	}
	public void setParent(LinkNode parent) {
		this.parent = parent;
	}
	public LinkNode getChild() {
		return child;
	}
	public void setChild(LinkNode child) {
		this.child = child;
	}
}

 

实现简单的增删查该双链表

public class NodeList {
	private static LinkNode head; 
	private static LinkNode foot = head;
	public static void main(String[] args) {
		NodeList list = new NodeList();
		list.createList();
		list.add("新元素0");
		list.add("新元素1");
		list.add("新元素2");
		list.add("新元素3");
		list.add(0, "插入元素");
		list.modify(3, "修改的");
		list.printList(head);
	}
	/**
	 * 创建链表
	 * @return
	 */
	public void createList() {
	}
	
	/**
	 * 添加元素
	 * @param obj ：插入的元素
	 */
	public void add(Object obj) {
		LinkNode node = new LinkNode(obj);
		if(head != null) {
			foot.setChild(node);
			node.setParent(foot);
			foot = node;
		} else {
			head = node;
			foot = head;
		}
		
	}
	/**
	 * 插入元素
	 * @param index ： 要插入元素的下标
	 * @param obj ：插入的元素
	 */
	public void add(int index, Object obj) {
		LinkNode node = new LinkNode(obj);//创建新结点
		if(index > this.size() || index < 0){
			throw new RuntimeException("下标越界") ;
		}
		if(head == null) {
				head = node;
				foot = head;
		} else {
			LinkNode node1 = this.getLinkNode(index);//得到当前位置的结点
			LinkNode node2 = node1.getChild();//子结点
			//设置新的引用关系
			node1.setChild(node);
			node.setParent(node1);
			
			node.setChild(node2);
			node2.setParent(node);
		}
		
	}
	
	/**
	 * 得到指定下标的元素
	 * @param index 下标
	 * @return 结点
	 */
	public LinkNode getLinkNode(int index){
		//System.out.println("<<<<<<"+this.size());
		if(index > this.size() || index < 0){
			throw new RuntimeException("下标越界") ;
		}
		if(head == null) {
			System.out.println("该链表为空！！！");
			return null;
		} else {
			int i = 0;
			LinkNode node = head;
			while (i < index) {
				node = node.getChild();
				i++;
			} 
			//System.out.println(node.getObject());
			return node;
			
		}	
	}
	/**
	 * 删除元素
	 */
	public void remove() {
		if(head == null) {
			System.out.println("无效，此链表为空");
		} else {
			LinkNode node = foot;//得到尾结点
			LinkNode node1 = foot.getParent();//得到前个结点
			//设置关系
			node1.setChild(null);
		}
	}
	/**
	 * 删除指定元素
	 * @param index ： 元素的下标
	 */
	public void remove(int index) {
		//判断下标
		if(index >= this.size() || index < 0){
			throw new RuntimeException("下标越界") ;
		} else {
			if(head == null) {
				System.out.println("无效，此链表为空");
			} else if(index < this.size() -1 && index > 0){
				LinkNode node = this.getLinkNode(index);//得到index的元素
				LinkNode node1 = node.getParent();//得到前结点
				LinkNode node2 = node.getChild();//得到后结点
				//设置关系
				node1.setChild(node2);
				node2.setParent(node1);
			} else {// 删除尾结点
				LinkNode no = foot;//得到尾结点
				LinkNode no1 = foot.getParent();//得到前个结点
				//设置关系
				no1.setChild(null);
				
			}
			
		}
		
	}
	/**
	 * 得到链表的大小
	 * @return 链表的大小
	 */
	public int size() {
		if(head != null) {
			int i = 0;
			LinkNode node = head;
			while(node.getChild() != null) {
				i++;
				node = node.getChild();
			}
			return i+1;
		} else {
			return 0;
		}
	}
	/**
	 * 更改指定下标的元素
	 * @param index 下标
	 * @param obj 新元素
	 */
	public void modify(int index, Object obj) {
		//判断下标
		if(index >= this.size() || index < 0){
			throw new RuntimeException("下标越界") ;
		} else {
			LinkNode node = new LinkNode(obj);//创建新结点
			if(head == null) {
				System.out.println("无效，此链表为空");
			} else if(index < this.size() -1){
				LinkNode nodeindex = this.getLinkNode(index);//得到index的元素
				LinkNode nodeahead = nodeindex.getParent();//得到前结点
				LinkNode nodebehind = nodeindex.getChild();//得到后结点
				//设置关系
				nodeahead.setChild(node);
				node.setParent(nodeahead);
				
				node.setChild(nodebehind);
				nodebehind.setParent(node);
			} else {// 删除尾结点
				LinkNode no = foot;//得到尾结点
				LinkNode noa = foot.getParent();
				
				noa.setChild(node);
				node.setParent(noa);
				
				node.setChild(null);
				
			}
		}
	}
	/**
	 * 遍历链表
	 */
	public void printList(LinkNode head) {
		if(head != null) {
			Object data = head.getObject();
			System.out.println(data);
			LinkNode temp = head.getChild();
			printList(temp);
		} 
	}
	
}

 

对于链表结点的操作时比较纠结的，一不小心就很容易混乱，所在使用时必须理清思路，一步步实现。