离散的存储空间——链表

2016.06.06


上课内容：链表


       前面我们有讲到数组队列，知道它的优点是查询快，元素是整块添加的，而与数组列表相反，链表添加很快，比较方便插入和删除操作，但它查询慢，元素是离散的。

       链表由一系列结点组成，结点可以在运动时动态生成。每个结点包括两个部分:一个是存储数据结构的数据域，另一个是存储下一个结点地址的指针。


      下面我们来介绍俩种链表。


      单链表：由两部分组成：

      一个是结点的数据，用data表示。

      另一个是结点指向的地址，用next表示。

      我们从一个根节点开始，它有一个data，当我们需要再建立一个节点时，把next指向下一个节点的地址，这样就达到了连接的效果。链表的好处就在于当创建一个节点时，就会开辟一段内存空间，删除一个节点时，就会释放一段内存空间。这样大大节省了内存空间。

    

        双向链表：由三部分组成：

        一个是该节点的数据，用data表示。

        一个存储直接子节点地址，一般称为右链域。        一个存储直接父节点地址，一般称之为左链域。

       下面我们举例说明：

public class Manager {	
	public static void main(String[] arg){
		//创建一个字符串的链表
		MyLinkList<String> list = new MyLinkList<String>();		
		//添加字符串
		list.add("hello");
		list.add(" ");
		list.add("world");		
		//获取所有的元素并且输出
		for(int i=0; i<list.getLength(); i++){
			System.out.print(list.get(i));
		}				
	}
}

 

public class Node<E> {
	//保存数据
	E data;

	//下一个节点
	Node<E> next;
	
	//根据数据新建节点
	Node(E e){
		data = e;
	}
	
	//无参的构造方法
	Node(){
		
	}
	
} 

 

public class MyLinkList<E> implements MyList<E>{
	//长度
	private int size;
	//头节点
	private Node<E> head;
	//尾节点
	private Node<E> tail;
	
	
	
	
	
	@Override
	public void add(E e) {
		//新建一个节点
		Node<E> newNode = new Node<E>(e);
		if(size == 0){//如果是第一个节点
			//头节点和尾节点都指向第一个节点
			head = newNode;
			tail = newNode;
		}else{
			//把新节点添加到末尾
			tail.next = newNode;
			//把尾节点修改为新节点
			tail = newNode;
		}
		//长度+1
		size++;
	}

	@Override
	public void delete(int index) {
		// TODO Auto-generated method stub
		
	}

	@Override
	public int getLength() {
		// TODO Auto-generated method stub
		return size;
	}

	@Override
	public void update(int index, E newE) {
		// TODO Auto-generated method stub
		
	}

	@Override
	public E get(int index) {//从头节点开始往后一个个的查询
		//新建一个节点，等于头节点
		Node<E> node = head;
		
		for(int i=0; i<index; i++){
			//往后移动一个
			node = node.next;
		}
				
		return node.data;
	}

}

 public interface MyList<E>{
	/**
	 * 添加一个元素
	 * @param e 需要添加的元素
	 */
	public void add(E e);
	
	/**
	 * 删除指定位置的元素
	 * @param index  需要删除元素的下标
	 */
	public void delete(int index);
	
	/**
	 * 获取元素个数
	 * @return 元素的个数
	 */
	public int getLength();
	
	/**
	 * 修改指定下标的元素
	 * @param index 需要修改的元素下标
	 * @param newE 新的元素
	 */
	public void update(int index,E newE);
	
	/**
	 * 获取指定下标的元素
	 * @param index 元素下标
	 * @return 需要获取的元素
	 */
	public E get(int index);
}

public class test {

	public Node createlink() {
		Node root = new Node();
		String s0 = "a";
		Object o = (String) s0;
		root.data = o;

		Node next1 = new Node();
		String s1 = "b";
		Object o1 = (String) s1;
		next1.data = o1;

		Node next2 = new Node();
		String s2 = "c";
		Object o2 = (String) s2;
		next2.data = o2;

		Node next3 = new Node();
		String s3 = "d";
		Object o3 = (String) s3;
		next3.data = o3;

		Node next4 = new Node();
		String s4 = "e";
		Object o4 = (String) s4;
		next4.data = o4;

		Node next5 = new Node();
		String s5 = "f";
		Object o5 = (String) s5;
		next5.data = o5;

		root.next = next1;
		next1.next = next2;
		next2.next = next3;
		next3.next = next4;
		next4.next = next5;

		return root;
	}

	public void println(Node root) {
		int i = 1;
		while (null != root) {
			Object data = root.data;
			root = root.next;

			System.out.println("第" + i + "个节点是" + data);
			i++;

		}
	}
	public Node delet(Node root, int index) {
		if (index == 1) {
			root = root.next;
			return root;
		} else {
			Node temp=root;
			for (int i = 1; i < index - 1; i++) {
				root = root.next;
			}
			root.next = root.next.next;
			return temp;
		}
		
	}	
	public static void main(String[] args) {
		test te = new test();
		Node root = te.createlink();
		te.println(root);
		root=te.delet(root, 3);
		te.println(root);
	
	}
}