文档章节

java 实现节点链表

蜀山下的鱼
 蜀山下的鱼
发布于 2015/04/29 00:44
字数 1100
阅读 32
收藏 1

 链结点  

   在链表中,每个数据项都被包含在‘点“中,一个点是某个类的对象,这个类可认叫做 

   LINK。因为一个链表中有许多类似的链结点,所以有必要用一个不同于链表的类来表达 

   链结点。每个 LINK 对象中都包含一个对下一个点引用的字段(通常叫做 next)但是

   本身的对象中有一个字段指向对第一个链结点的引用  

单链表是一种顺序存取的结构,为找第 i个数据元素,必须先找到第 i-1个数 

据元素。因此,查找第i个数据元素的基本操作为:移动指针,比较  j                     和  

    1、链接存储方法 

    链接方式存储的线性表简称为链表(LinkedList )。 

    链表的具体存储表示为: 

    ① 用一组任意的存储单元来存放线性表的结点(这组存储单元既可以是连续的, 

也可以是不连续的) 

 ② 链表中结点的逻辑次序和物理次序不一定相同。为了能正确表示结点间的逻 

辑关系,在存储每个结点值的同时,还必须存储指示其后继结点的地址(或位置)信 

息(称为指针(pointer )或链(link) ) 

    注意: 

    链式存储是最常用的存储方式之一,它不仅可用来表示线性表,而且可用来表示 

各种非线性的数据结构。 

    2 、链表的结点结构 

     ┌──┬──┐ 

     │data next │ 

     └──┴──┘ 

    data --存放结点值的数据域 

    next --存放结点的直接后继的地址(位置)的指针域(链域) 

    注意: 

    ①链表通过每个结点的链域将线性表的 个结点按其逻辑顺序链接在一起的。 

    ②每个结点只有一个链域的链表称为单链表(Single                         Linked  List )。 

    3 、头指针 head 和终端结点指针域的表示 

    单链表中每个结点的存储地址是存放在其前趋结点 next 域中,而开始结点无前 

趋,故应设头指针 head 指向开始结点。 

    注意: 

    链表由头指针唯一确定,单链表可以用头指针的名字来命名。 

    【例】头指针名是 head 的链表可称为表 head 。 

    终端结点无后继,故终端结点的指针域为空,即 NULL 

 

 

 

public class LinkList<T> {

    public class Node{  //定义节点
        private T data;
        private Node next;
        public Node(){
            
        }
        public Node(T data,Node next){
            this.data=data;
            this.next=next;
        }
    }
    
    private Node header;//头节点
    private Node tail;//尾节点
    private int size;//链表大小
    
   
    //构造函数初始化数据
    public LinkList(){
        header=null;
        tail=null;
    }
    public LinkList(T element){
        header=new Node(element,null);
        tail=header;
        size++;
    }
    
    //链表长度
    public int length(){
        return size;
    }
    
    //返回指定位置index的节点
    public T get(int index){
        return getNodeByIndex(index).data;
    }
    
    private Node getNodeByIndex(int index) {
        if(index<0||index>size-1){
            throw new IndexOutOfBoundsException("线性表索引越界");
        }
        Node current=header;
        for(int i=0;i<size&¤t!=null;i++,current=current.next){
            if(i==index){
                return current;
            }
        }
        return null;
    }
    
    //返回element在链表的位置,-1表示不存在
    public int locate(T element){
        Node current=header;
        for(int i=0;i<size&¤t!=null;i++,current=current.next){
            if(current.data==element){
                return i;
            }
        }
        return -1;
    }
    
    
    //在index位置插入节点element
    public void insert(T element,int index){
        if(index<0||index>size){
            throw new IndexOutOfBoundsException("线性表索引越界");
        }
        if(header==null){
            add(element);
        }else{
            if(index==0){
                addAtHeader(element);
            }else{
                Node prev=getNodeByIndex(index-1);
                prev.next=new Node(element,prev.next);
                size++;
            }
        }
    }
    
    //采用尾插法为链表添加新节点
    private void add(T element) {
        // TODO Auto-generated method stub
        if(header==null){
            header=new Node(element,null);
            tail=header;
        }else{
            Node newNode=new Node(element,null);
            tail.next=newNode;
            tail=newNode;
        }
        size++;
    }
    
    //采用头插法为链表添加新节点
    private void addAtHeader(T element){
        header=new Node(element,header);
        if(tail==null){
            tail=header;
        }
        size++;
    }
    
    //删除index位置的节点
    public T delete(int index){
        if(index<0||index>size-1){
            throw new IndexOutOfBoundsException("线性表索引越界");
        }
        Node del=null;
        if(index==0){
            del=header;
            header=header.next;
        }else{
            Node prev=getNodeByIndex(index-1);
            del=prev.next;
            prev.next=del.next;
            del.next=null;
        }
        size--;
        return del.data;
    }
    
    //从链表后面删除一个节点
    public T remove(){
        return delete(size-1);
    }
    
    //是否为空
    public boolean empty(){
        return size==0;
    }
    //清空链表
    public void clear(){
        header=null;
        tail=null;
        size=0;
    }
    
    public String toString(){
        if(empty()){
            return "[]";
        }else{
            StringBuilder sb=new StringBuilder("[");
            for(Node current=header;current!=null;current=current.next){
                sb.append(current.data.toString()+", ");
            }
            int len=sb.length();
            return sb.delete(len-2, len).append("]").toString();
        }
    }
    public static void main(String[] args) {
        LinkList<String> list=new LinkList<String>();
        list.insert("aaa", 0);
        list.add("bbb");
        list.add("ccc");
        System.out.println(list.toString());
        list.insert("ddd", 1);
        System.out.println(list.toString());
        list.delete(2);
        System.out.println(list.toString());
        System.out.println("ccc在链表中的位置:"+list.locate("ccc"));
        System.out.println("链表中索引2处的元素:"+list.get(2));
    }

}

本文转载自:http://blog.csdn.net/caiwenfeng_for_23/article/details/8496029

蜀山下的鱼
粉丝 9
博文 405
码字总数 0
作品 0
广州
高级程序员
私信 提问
JDK源码之LinkedList

LinkedList简介 LinkedList 是一个继承于AbstractSequentialList的双向链表。它也可以被当作堆栈、队列或双端队列进行操作。 LinkedList 实现 List 接口,能对它进行队列操作。 LinkedList 实...

村长大神
2014/03/27
0
0
源码之LinkedList 单双向链表介绍

链表 单向链表 单链表的特点: 最后一个节点的next为null(闭环链表指向第一个元素) 只可一个方向遍历 双向链表 特点: 最后一个节点的next为null(闭环链表指向第一个元素) 可双向遍历(从头部...

yimingkeji
01/07
0
0
算法和编程面试题精选TOP50!(附代码+解题思路+答案)

作者 | javinpaul 编译 | 王天宇、Jane 整理 | Jane 出品 | AI科技大本营 【导读】之前我们给同学们推荐了很多关于 Python 的面试资源,大家都表示很有用。这次营长表示要翻 Java 的牌子啦~...

AI科技大本营
2018/09/27
0
0
算法和编程面试题精选 TOP50!(附代码+解题思路+答案)

作者 | javinpaul 出品 | AI科技大本营 数组 数组,将元素存储到内存的连续位置中,是最基本的数据结构。在任何和编程相关的面试中,都会被问到和数组相关的问题,可以说是非常热门的考题之一...

CSDN资讯
2018/10/02
0
0
聊聊LinkedHashMap

LinkedHashMap简介 LinkedHashMap是一个根据某种规则有序的hashmap。根据名字,我们也可以看出这个集合是有hash散列的功能的同时也有顺序。hashmap是无法根据某种顺序来访问数据的,例如放入...

xpbob
2018/11/12
0
0

没有更多内容

加载失败,请刷新页面

加载更多

好程序员分享placeholder属性详解

  好程序员分享placeholder属性详解,HTML5里新引入很多有趣的新特征;有些体现在HTML里,有些是JavaScript API,全部非常的有用。其中我最喜欢的一个特征就是文本框(INPUT)里的placehold...

好程序员IT
26分钟前
0
0
[学]ngin反向代理搭建与配置

Nginx安装地址:https://www.cnblogs.com/wyd168/p/6636529.html (linux) 必须安装的4个包: nginx-1.1.10.tar.gz openssl-1.0.1t.tar.gz pcre-8.39.tar.gz zlib-1.2.11.tar.gz ng配置主要......

覃光林
30分钟前
1
0
互联网商城的上云改造之旅

在中国,经过十年的发展,云计算产业已走过概念普及的1.0时期,进入“上云”和落地的2. 0阶段,企业上云意识不断增强,越来越多的企业选择部署多云和混合IT。 如今,云计算生态一片繁荣,看似...

zhaowei121
31分钟前
0
0
fastJson 一些小例子

package com.*;import com.alibaba.fastjson.annotation.JSONField;public class VO { @JSONField(name="ID") private int id; public int getId() { ......

qimh
45分钟前
1
0
十年后,程序员的工资还能达到现在的水平吗?

一方面,程序员的门槛正在逐渐消失,因为计算机相关专业毕业生一年比一年多; IT 培训班出来的学生一年比一年多;网络上各种编程课程,也正在帮助无数人零基础转型软件开发…… 另一方面,程...

爱编程的浪子
53分钟前
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部