开发者社区> 傲海> 正文

【算法数据结构Java实现】Java实现单链表

简介: 1.背景           单链表是最基本的数据结构,仔细看了很久终于搞明白了,差不每个部分,每个链都是node的一个对象。需要两个参数定位:一个是index,表示对象的方位。另一个是node的对象。 2.代码 node类 public class Node { protected Node next; protected int data; public Node(in
+关注继续查看

1.背景

          单链表是最基本的数据结构,仔细看了很久终于搞明白了,差不每个部分,每个链都是node的一个对象。需要两个参数定位:一个是index,表示对象的方位。另一个是node的对象。



2.代码


node类
public class Node {
	 protected Node next;
	 protected int data;
	 public Node(int data){
		 this.data=data;
	 }
	 public void display(){
     System.out.print(data+"");
   }
}

arraylist类
public class myArrayList {
      public Node first;//定义头结点
      private int pos=0;//节点位置
      public myArrayList(){
    	  // this.first=null;
      }
      //插入一个头结点
      public void addFirstNode(int data){
    	    Node node=new Node(data);
    	    node.next=first;
    	    first=node;
      }
      //删除头结点
      public Node deleteFirstNode(){
    	    Node tempNode=first;
    	    first=tempNode.next;
    	    return tempNode;
      }
      // 在任意位置插入节点 在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;  
      }  
      // 删除任意位置的节点  
      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;  
      }     
      public void displayAllNodes() {  
          Node current = first;  
           while (current != null) {  
              current.display();
              System.out.println();
              current = current. next;  
          }            
     }  
      
}


实现的main函数:
public class Main {
   public static void main(String args[]){
	   myArrayList ls=new myArrayList();   	  
	   ls.addFirstNode(15);	   
	   ls.addFirstNode(16);
	   ls.add(1, 144);
	   ls.add(2, 44);
	   ls.deleteByPos(1);
	  ls.displayAllNodes();	   
   }
}



实现结果:

16

44

15


package LinkedList;   
  
/**  
 * <p><strong>我的Java单链表练习</strong></p>  
 * <p>单链表提供了在列表头的高效插入和删除操作,不过在单链表的末尾的插入操作效率很低.</p>  
 * <p>单链表指针域保存着下一节点的引用,尾结点的指针域等于null</p>  
 * @author baby69yy2000  
 */  
public class SingleLinkedList<T> {   
       
    /**  
     * 结点类  
     */  
    private static class Node<T> {   
        T nodeValue; // 数据域   
        Node<T> next; // 指针域保存着下一节点的引用   
           
        Node(T nodeValue, Node<T> next) {   
            this.nodeValue = nodeValue;   
            this.next = next;   
        }   
           
        Node(T nodeValue) {   
            this(nodeValue, null);   
        }   
    }   
  
    // 下面是SingleLinkedList类的数据成员和方法   
    private Node<T> head, tail;   
       
    public SingleLinkedList() {   
        head = tail = null;   
    }   
       
    /**  
     * 判断链表是否为空  
     */  
    public boolean isEmpty() {   
        return head == null;   
    }   
       
    /**  
     * 创建头指针,该方法只用一次!  
     */  
    public void addToHead(T item) {   
        head = new Node<T>(item);   
        if(tail == null) tail = head;   
    }   
       
    /**  
     * 添加尾指针,该方法使用多次  
     */  
    public void addToTail(T item) {   
        if (!isEmpty()) { // 若链表非空那么将尾指针的next初使化为一个新的元素   
            tail.next = new Node<T>(item); // 然后将尾指针指向现在它自己的下一个元素   
            tail = tail.next;   
        } else { // 如果为空则创建一个新的!并将头尾同时指向它   
            head = tail = new Node<T>(item);         
        }   
    }   
       
    /**  
     * 打印列表  
     */  
    public void printList() {   
        if (isEmpty()) {   
            System.out.println("null");   
        } else {   
            for(Node<T> p = head; p != null; p = p.next)   
                System.out.println(p.nodeValue);   
        }   
    }   
       
    /**  
     * 在表头插入结点,效率非常高  
     */  
    public void addFirst(T item) {   
        Node<T> newNode = new Node<T>(item);   
        newNode.next = head;   
        head = newNode;   
    }   
       
    /**  
     * 在表尾插入结点,效率很低  
     */  
    public void addLast(T item) {   
        Node<T> newNode = new Node<T>(item);   
        Node<T> p = head;   
        while (p.next != null) p = p.next;   
        p.next = newNode;   
        newNode.next = null;   
    }   
       
    /**  
     * 在表头删除结点,效率非常高  
     */  
    public void removeFirst() {   
        if (!isEmpty()) head = head.next;   
        else System.out.println("The list have been emptied!");   
    }   
       
    /**  
     * 在表尾删除结点,效率很低  
     */  
    public void removeLast() {   
        Node<T> prev = null, curr = head;   
        while(curr.next != null) {   
            prev = curr;   
            curr = curr.next;   
            if(curr.next == null) prev.next = null;   
        }   
    }   
       
    /**  
     * <p>插入一个新结点</p>  
     * <ul>插入操作可能有四种情况:  
     * <li>①表为空, 返回false</li>  
     * <li>②表非空,指定的数据不存在</li>  
     * <li>③指定的数据是表的第一个元素</li>  
     * <li>④指定的数据在表的中间</li></ul>  
     * @param appointedItem 指定的nodeValue  
     * @param item 要插入的结点  
     * @return 成功插入返回true;  
     */  
    public boolean insert(T appointedItem, T item) {   
        Node<T>  prev = head, curr = head.next, newNode;   
        newNode = new Node<T>(item);   
        if(!isEmpty()) {   
            while((curr != null) && (!appointedItem.equals(curr.nodeValue))) { //两个判断条件不能换   
                prev = curr;   
                curr = curr.next;   
            }   
            newNode.next = curr; //②③④   
            prev.next = newNode;   
            return true;    
        }   
        return false; //①   
    }   
       
    /**  
     * <p>移除此列表中首次出现的指定元素</p>  
     * <ul>删除操作可能出现的情况:  
     * <li>①prev为空,这意味着curr为head. head = curr.next; --> removeFirst();</li>  
     * <li>②匹配出现在列表中的某个中间位置,此时执行的操作是 --> prev.next = curr.next;,</li></ul>  
     * <p>在列表中定位某个结点需要两个引用:一个对前一结点(prev左)的引用以及一个对当前结点(curr右)的引用.</p>  
     * prev = curr;  
     * curr = curr.next;  
     */  
    public void remove(T item) {   
        Node<T> curr = head, prev = null;   
        boolean found = false;   
        while (curr != null && !found) {   
            if (item.equals(curr.nodeValue)) {   
                if(prev == null) removeFirst();   
                else prev.next = curr.next;   
                found = true;   
            } else {   
                prev = curr;   
                curr = curr.next;   
            }   
        }   
    }   
       
    /**  
     * 返回此列表中首次出现的指定元素的索引,如果列表中不包含此元素,则返回 -1.  
     */  
    public int indexOf(T item) {   
        int index = 0;   
        Node<T> p;   
        for(p = head; p != null; p = p.next) {   
            if(item.equals(p.nodeValue))   
                return index;   
            index++;   
                   
        }   
        return -1;   
    }   
       
    /**  
     * 如果此列表包含指定元素,则返回 true。  
     */  
     public boolean contains(T item) {   
         return indexOf(item) != -1;   
     }   
       
    public static void main(String[] args) {   
        SingleLinkedList<String> t = new SingleLinkedList<String>();   
        t.addToHead("A");   
        //t.addFirst("addFirst");   
        t.addToTail("B");   
        t.addToTail("C");   
        System.out.println(t.indexOf("C")); // 2   
        System.out.println(t.contains("A")); // true   
        //t.addLast("addLast");   
        //t.removeLast();   
        //t.insert("B", "insert");   
        //t.removeFirst();   
        //t.remove("B"); // A C   
        t.printList(); // A B C   
           
    }   
  
}  



/********************************

* 本文来自博客  “李博Garvin“

* 转载请标明出处:http://blog.csdn.net/buptgshengod

******************************************/


版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
Java实现单词计数MapReduce
本文分享实现单词计数MapReduce的方法
134 0
JAVA 实现上传图片添加水印(详细版)(上)
JAVA 实现上传图片添加水印(详细版)
279 0
Java 实现汉字按照首字母分组排序
Java 实现汉字按照首字母分组排序
195 0
Java实现图书管理系统
本篇文章是对目前Java专栏已有内容的一个总结练习,希望各位小主们在学习完面向对象的知识后,可以阅览本篇文章后,自己也动手实现一个这样的demo来加深总结应用已经学到知识并进行巩固。
178 0
java实现spring boot项目启动时,重启Windows进程
java实现spring boot项目启动时,重启Windows进程
287 0
Java实现拼图小游戏(1)—— JFrame的认识及界面搭建
如果要在某一个界面里面添加功能的话,都在一个类中,会显得代码难以阅读,而且修改起来也会很困难,所以我们将游戏主界面、登录界面、以及注册界面都单独编成一个类,每一个类都继承JFrame父类,并且在类中创建方法来来实现页面
184 0
Java网络编程:UDP/TCP实现实时聊天、上传图片、下载资源等
ip地址的分类: 1、ipv4、ipv6 127.0.0.1:4个字节组成,0-255,42亿;30亿都在北美,亚洲就只有4亿 2011年就用尽了。
132 0
Java实现拼图小游戏(7)—— 计步功能及菜单业务的实现
注意由于我们计步功能的步数要在重写方法中用到,所以不能将初始化语句写在方法体内,而是要写在成员位置。在其名字的时候也要做到“见名知意”,所以我们给它起名字为step
99 0
Java实现拼图小游戏(7)—— 作弊码和判断胜利
当我们好不容易把拼图复原了,但是一点提示也没有,完全看不出来是成功了,那么我们就需要有判断胜利的功能去弹出“成功”类的图片,以便于玩家选择是重新开始还是退出小游戏
104 0
Java实现拼图小游戏(7)——查看完整图片(键盘监听实例2)
由于在移动和图片中我们已经添加了键盘监听,也继承了键盘监听的接口,那么我们只需要在重写方法内输入我们的代码即可
65 0
+关注
傲海
著有《机器学习实践应用》,阿里云机器学习PAI产品经理,个人微信公众号&ldquo;凡人机器学习&rdquo;。
文章
问答
视频
文章排行榜
最热
最新
相关课程
更多
相关电子书
更多
JAVA开发手册1.5.0
立即下载
低代码开发师(初级)实战教程
立即下载
阿里巴巴DevOps 最佳实践手册
立即下载
相关实验场景
更多