算法最简单之_链表

忘是亡心i 2022-09-25 00:20 263阅读 0赞

node类：

//节点类  
    public class Node {  
         protected Node next; //指针域  
         protected int data;//数据域  
           
         public Node( int data) {  
               this. data = data;  
         }  
           
         //显示此节点  
         public void display() {  
              System. out.print( data + " ");  
         }  
    }

（一）单链表

1）构造链表

![20160803162047621][]

2）链表头插入

![20160803162243740][]

// 插入一个头节点  
    public void addFirstNode( int data) {  
         Node node = new Node(data);  
         node. next = first;  
         first = node;  
    }

3）链表头删除

只需要 first = first.next 即可

![20160803162421493][]

// 删除一个头结点,并返回头结点  
    public Node deleteFirstNode() {  
         Node tempNode = first;  
         first = tempNode. next;  
         return tempNode;  
    }

4）链表任意位置添加

添加位置前后断开，分别指向对应的引用即可

![20160803163247895][]

// 在任意位置插入节点 在index的后面插入  
    public void add(int index, int data) {  
        Node node = new Node(data);  
        Node current = first;  
        Node previous = first;  
         while ( pos != index) {  
            previous = current;  
            current = current. next;  
             pos++;  
        }  
        node. next = current;  
        previous. next = node;  
         pos = 0;  
    }

5）任意位置删除

![20160803163558165][]

// 删除任意位置的节点  
    public Node deleteByPos( int index) {  
        Node current = first;  
        Node previous = first;  
         while ( pos != index) {  
             pos++;  
            previous = current;  
            current = current. next;  
        }  
         if(current == first) {  
             first = first. next;  
        } else {  
             pos = 0;  
            previous. next = current. next;  
        }  
         return current;  
    }

6）链表遍历

// 显示出所有的节点信息  
    public void displayAllNodes() {  
        Node current = first;  
        while (current != null) {  
             current.display();  
             current = current. next;  
        }  
        System.out.println();  
    }

7）根据位置和根据节点查找

![20160803170239123][]

// 根据位置查找节点信息  
         public Node findByPos( int index) {  
              Node current = first;  
               if ( pos != index) {  
                  current = current. next;  
                   pos++;  
              }  
               return current;  
         }  
      
         // 根据数据查找节点信息  
         public Node findByData( int data) {  
              Node current = first;  
               while (current. data != data) {  
                   if (current. next == null)  
                        return null;  
                  current = current. next;  
              }  
               return current;  
         }

（一）双链表

1）它是这样的

![Center][]

2）双链表整体鸟览

![Center 1][]

3）双链表添加

![Center 2][]

4）双链表删除

![Center 3][]

5）双链表代码

/**
     * 双向链表
     * @author yl
     *
     */
    public class LinkNode {
    	private Object obj;
    	private LinkNode child;
    	private LinkNode parent;
     
    	public LinkNode(Object obj){
    		this.obj=obj;
    	}
    	 
    	//定义方法
    	public Object getObj(){
    		return obj;
    	}
    	public void setObj(Object obj){
    		this.obj=obj;
    	}
    	public LinkNode getChild(){
    		return child;
    	}
    	public void setChild(LinkNode child){
    		this.child=child;
    	}
    	public LinkNode getParent(){
    		return parent;
    	}
    	public void setParent(LinkNode parent){
    		this.parent=parent;
    	}
    }
    再来对这个链表进行测试：
    package cn.链表;
    /**
     * 双向链表的测试
     * @author Administrator
     *
     */
    public class LinkListTest {
    	private static LinkNode front=null;
    	private LinkNode last=front;
    	public static void main(String args[]){
    		LinkListTest list=new LinkListTest();
    		list.add("头结点");
    		for(int i=0;i<10;i++){
    		list.add("结点"+i);
    		}
    		//测试指定位置下取得结点
    		Object obj=list.getLinkNode(3).getObj();
    		//测试在指定位置插入元素
    		list.add(3, "新来的元素");
    		System.out.println("<><><><><><><>"+obj);
    		list.printLinkNode(front);
    		System.out.println("<><><><><><><><><><><><><><><><><><><><><");
    		// list.remove(3);
    		// list.printLinkNode(front);
    		list.upDate(3, "值被改变的元素");
    		list.printLinkNode(front);
    		System.out.println("<><><><><><><><><><><><><><><><><><><><><");
    		list.printLinkNode1(3);
    	 
    	}
    	/**
    	 * 在链表的后面插入元素
    	 * @param obj
    	 */
    	public void add(Object obj){
    		//根据给定的值创建结点
    		LinkNode node=new LinkNode(obj);
    		if(front==null){
    		//如果链表为空的时候
    		// front.setChild(node);
    		// node.setParent(front);
    		//第一个结点也即是最后一个结点
    		front=node;
    		last=front;
    		// System.out.println(front.getObj());
    	}
    	else{
    		//新插入的结点为最后一个结点
    		last.setChild(node);
    		node.setParent(last);
    		last=node;
    		}
    	}
    	/**
    	 * 在指定位置插入元素
    	 * @param index
    	 * @param obj
    	 */
    	public void add(int index,Object obj){
    		//先创建结点
    		LinkNode node=new LinkNode(obj);
    		//判断传入的下标
    		if(index<0||index>size()){
    			throw new RuntimeException("下标越界：size："+size()+"index："+index);
    		}else{
    			//传入的下标符合要求
    			if(front==null){
    				//如果链表为空的时候
    				front=node;
    				last=front;
    			}else if(index==size()){
    				add(node);
    			}else{
    				//链表不为空,取得当前下标的结点
    				LinkNode nownode=getLinkNode(index);
    				//得到父结点
    				LinkNode fnode=nownode.getParent();
    				//重新定义新的引用关系
    				fnode.setChild(node);
    				node.setParent(fnode);
    				 
    				node.setChild(nownode);
    				nownode.setParent(node);
    			}
    		}
    	}
    	/**
    	 * 根据下标，删除当前的结点
    	 * @param index
    	 */
    	public void remove(int index){
    		if(index<0||index>size()){
    			throw new RuntimeException("下标越界：size："+size()+"index："+index);
    		}else{
    			//传入的下标符合要求
    			if(front==null){
    				//如果链表为空的时候
    				System.out.println("链表为空，不能删除元素啦！！！");
    			}
    			else{
    				//链表不为空,取得当前下标的结点
    				LinkNode nownode=getLinkNode(index);
    				//得到父结点
    				LinkNode fnode=nownode.getParent();
    				//得到父结点
    				LinkNode cnode=nownode.getChild();
    				//重新定义新的引用关系
    				fnode.setChild(cnode);
    				cnode.setParent(fnode);
    			}
    		}
    	}
    	/**
    	 * 根据下标取得当前的结点
    	 * @param index 下标值
    	 * @return
    	 */
    	public LinkNode getLinkNode(int index){
    		//判断传入的下标
    		if(index<0||index>size()){
    			throw new RuntimeException("下标越界：size："+size()+"index："+index);
    		}else{
    			//先取得头结点
    			LinkNode node=front;
    			int i=0;
    			while(i<index){
    				i++;
    				node=node.getChild();
    			}
    			return node;
    		}
    	}
    	/**
    	 * 在指定的位置，更新该结点，结点的值为obj
    	 * @param index
    	 * @param obj 更改的结点的值
    	 */
    	public void upDate(int index,Object obj){
    		if(index<0||index>size()){
    			throw new RuntimeException("下标越界：size："+size()+"index："+index);
    		}else{
    			//传入的下标符合要求
    			if(front==null){
    				//如果链表为空的时候
    				System.out.println("链表为空，不能更新元素啦！！！");
    			}
    			else{
    				//链表不为空,取得当前下标的结点
    				LinkNode nownode=getLinkNode(index);
    				//给结点重新赋值
    				nownode.setObj(obj);
    			}
    		}
    	}
    	/**
    	 * 得到链表的长度
    	 * @return
    	 */
    	public int size(){
    		if(front==null){
    			//链表为空
    			return 0;
    		}else{
    			//不为空
    			LinkNode node=front;
    			int count=0;
    			while(node!=null){
    				count++;
    				node=node.getChild();
    			}
    			return count;
    		}
    	}
    	/**
    	 * 打印链表
    	 * @param node 传入链表的头结点
    	 */
    	public void printLinkNode(LinkNode node){
    		if(front==null){
    			System.out.println("此链表为空！！！");
    		}else{
    			//先取得头结点
    			LinkNode n=front;
    			//遍历链表
    			while(n!=null){
    				Object obj=n.getObj();
    				System.out.println(obj);
    				n=n.getChild();
    			}
    		}
    	}
    	/**
    	 * 根据指定的位置来前后遍历
    	 * @param index
    	 */
    	public void printLinkNode1(int index){
    		if(index<0||index>size()){
    			throw new RuntimeException("下标越界：size："+size()+"index："+index);
    		}
    	 
    		LinkNode nownode=getLinkNode(index);
    		LinkNode cnode=nownode.getChild();
    		int i=index;
    		//往前遍历
    		while(nownode!=null&&i>=0){
    			Object obj=nownode.getObj();
    			System.out.println(obj);
    			i--;
    			nownode=nownode.getParent();
    		}
    		nownode=getLinkNode(index);
    		//往后遍历
    		while(nownode!=null&&i<size()){
    			Object obj=nownode.getObj();
    			System.out.println(obj);
    			i++;
    			nownode=nownode.getChild();
    		}
    	}
    }

参考：

http://blog.csdn.net/tayanxunhua/article/details/11100097/

http://hiliangliang1130-126-com.iteye.com/blog/1144023

http://www.cnblogs.com/xilifeng/archive/2012/10/06/2713185.html

http://blog.sina.com.cn/s/blog\_7d44748b01013fsf.html

[20160803162047621]: /images/20220719/ceb44917a78043148795c7f96ffe5775.png
[20160803162243740]: /images/20220719/4745b82e087342f6bfc4f75c9d3d2940.png
[20160803162421493]: /images/20220719/1c407a63158b4b998d54a112bc599cef.png
[20160803163247895]: /images/20220719/63fb72556f3c4c5d883ac292f99cbc8d.png
[20160803163558165]: /images/20220719/8fb0e243adb843269dc7bd5de94bcdc8.png
[20160803170239123]: /images/20220719/647e969f5070411897e1fcc509d1d896.png
[Center]: /images/20220719/a77de423615145ef9a2abb1d7c447889.png
[Center 1]: /images/20220719/ae46e2703df14277ba0815161e9b52ba.png
[Center 2]: /images/20220719/623627abb07c48d1a39bcfd750ae3d7c.png
[Center 3]: /images/20220719/1f579dcc42d74b5f87ce3cb824d3da2a.png