大话数据结构(八)Java程序——双向链表的实现

线性链表——双向链表

双向链表定义:

双向链表(double linked list): 是在单表单的每个结点中,再设置一个指向前驱结点的指针域。因此,在双向链表中的结点都有两个指针域,一个指向前驱,一个指向后继。

双向链表的存储结构

typedef struts DulNode{

Element data;

Struct DulNode *prior;前驱指针

Struct DulNode *next;后继指针

}DulDouble, *DulLinkList;

双向链表的插入与删除

双向链表的插入:

假设结点为s,要将结点插入到结点p和p->next中,我们需要下面几步:

s.prev = p;

s.next = p.next;

p.next.prev = s;

p.next = s;

总结起来就是:先搞定s的前驱后继,再搞定后结点的前驱,最后解决前驱结点的后继

双向链表的删除:

要删除p结点,只需要两个步骤:

p.next.prev = p.prev;

p.prev.next = p.next;

free(p);

总结:

相对于单链表,双向链表多了一个指针域,空间上要占用略多一点,但它有很好的对称性,使得对某个结点的前后结点操作更容易,可以提高算法的时间性能,这是牺牲空间换取的。

Java程序实现双链表:

package com.aclie.dataStructe4.sqeList;

public class MyDoubleLinkList {
    private int length =0;//当前长度
    private Node head;//头结点
    private Node tail;//当前结点结点

    public MyDoubleLinkList(){
        initLink();
    }
    public void initLink(){
        head  = new Node(null);
        tail = new Node(null);
        this.head = tail;
        length++;
    }

    //获取链表长度
    public int getSize(){
        return length;
    }
    //判断链表是否为空
    public boolean getEmpty(){
        return getSize()==0;
    }
    //根据索引查找元素  从第一个有效值开始
    public Node getNode(int index){
        Node p;
        if(index < 0 || index > length ){
            System.out.println("参数错误");
        }
        if(index < this.length/2){
            p = this.head;
            for(int i=0; i<index; i++){
                p = p.next;
            }
        }else{
            p = this.tail;
            for(int i= length; i>index;i--){
                p = p.prev;
            }
        }
        return p;
    }

    public Object getData(int index){
        return getNode(index).data;
    }

    //在头结点处插入
    public boolean addHead(Object e){
        //前驱引用为null,后继为node
        Node node = new Node(e, null, this.head);
        //改变头结点的前驱后继
        this.head.prev = node;
        this.head = node;
        if(tail == null){
            tail =  this.head;
        }
        length++;
        return true;
    }
    //在尾结点插入
    public boolean addTail(Object e){
        if(this.head == null){
            this.head = new Node(e,null,null);
            this.tail = this.head;
        }else{
            Node node = new Node(e,this.tail,null);
            this.tail.next = node;
            this.tail = node;

        }
        length++;
        return true;

    }
    //在指定位置插入元素
    public boolean addData(int index,Object ele){
        if(index <0 || index > this.length){
            System.out.println("参数错误");
        }
        if(this.head == null){
            this.addTail(ele);//用尾插法
        }else{
            if(index == 0){
                addHead(ele);//用头插法
            }else{
                Node p = this.getNode(index);//要插入处的结点
                Node n = p.next;
                Node node = new Node(ele,p,n);//要插入的结点
                n.prev = node;
                p.next = node;
                length ++;

            }
        }

        return true;
    }

    public void removeData(int index){
        if(index < 0 || index > length){
             System.out.println("参数错误");
         }else{
             Node del = null;
             if(index == 0){
                 del = this.head;
                 this.head = this.head.next;
                 this.head.prev = null;
                 length--;
             }else if(index == (length-1)){
                     Node p = this.getNode(index-1);//得到要删除结点的前驱结点
                     del = p.next;//要删除的结点
                     p.next = del.next;
                     if(del.next != null){
                         del.next.prev = p;
                     }
                     del.next = null;
                     del.prev = null;
                     length --;

                     this.tail.next = null;
                     this.tail.prev = p;
                     this.tail = p;
                 }
             else{
                     Node p = this.getNode(index-1);//要删除结点的前驱结点
                     del = p.next;//要删除的结点
                     p.next = del.next;
                     if(del.next != null){
                         del.next.prev = p;
                     }
                     del.prev = null;
                     del.next = null;
                     length--;
                 }

         }
    }
    //打印所有链表中的元素
    public void print(){
        Node current = this.head;
        while(current != null){
            System.out.println(current.data);
            current = current.next;
        }
    }
    //反向打印链表
    public void reversePrint(){
        Node current = this.tail;
        while(current != null){
            System.out.println(current.data);
            current = current.prev;
        }
    }
    public static void main(String args[]){
        MyDoubleLinkList linkList = new MyDoubleLinkList();
        linkList.addHead("aaaa");
//        System.out.println(linkList.getData(1));
        linkList.addTail("bbbb");
//        System.out.println(linkList.getData(3));
        linkList.addData(2, "eeee");
//        linkList.print();
        linkList.removeData(2);
        linkList.print();
        System.out.println(".....");
        linkList.reversePrint();
    }

}
class Node{
    Node prev;//指针域中前驱
    Node next;//指针域中后继
    Object data;//数据域
    public Node(Node current){
        prev = current;
        next = current;
    }
    //双链表前驱后继及数字域
    public Node(Object d, Node p,Node n){
        this.data = d;
        this.prev = p;
        this.next = n;
    }
    public Node getPrev() {
        return prev;
    }
    public void setPrev(Node prev) {
        this.prev = prev;
    }
    public Node getNext() {
        return next;
    }
    public void setNext(Node next) {
        this.next = next;
    }

}
时间: 11-17

大话数据结构(八)Java程序——双向链表的实现的相关文章

Java程序猿学习当中各个阶段的建议

回答阿里社招面试如何准备,顺便谈谈对于Java程序猿学习当中各个阶段的建议 引言 其实本来真的没打算写这篇文章,主要是LZ得记忆力不是很好,不像一些记忆力强的人,面试完以后,几乎能把自己和面试官的对话都给记下来.LZ自己当初面试完以后,除了记住一些聊过的知识点以外,具体的内容基本上忘得一干二净,所以写这篇文章其实是很有难度的. 但是,最近问LZ的人实在是太多了,为了避免重复回答,给自己省点力气,干脆就在这里统一回复了. 其实之前LZ写过一篇文章,但是那篇文章更多的是在讨论“面试前该不该刷题”这个

To Java程序员:切勿用普通for循环遍历LinkedList

ArrayList与LinkedList的普通for循环遍历 对于大部分Java程序员朋友们来说,可能平时使用得最多的List就是ArrayList,对于ArrayList的遍历,一般用如下写法: public static void main(String[] args) { List<Integer> arrayList = new ArrayList<Integer>(); for (int i = 0; i < 100; i++) arrayList.add(i);

To Java程序员:切勿用普通for循环遍历LinkedList(转)

ArrayList与LinkedList的普通for循环遍历 对于大部分Java程序员朋友们来说,可能平时使用得最多的List就是ArrayList,对于ArrayList的遍历,一般用如下写法: public static void main(String[] args) { List<Integer> arrayList = new ArrayList<Integer>(); for (int i = 0; i < 100; i++) arrayList.add(i);

Java程序员面试准备

其实本来真的没打算写这篇文章,主要是LZ得记忆力不是很好,不像一些记忆力强的人,面试完以后,几乎能把自己和面试官的对话都给记下来.LZ自己当初面试完以后,除了记住一些聊过的知识点以外,具体的内容基本上忘得一干二净,所以写这篇文章其实是很有难度的. 但是,最近问LZ的人实在是太多了,为了避免重复回答,给自己省点力气,干脆就在这里统一回复了. 其实之前LZ写过一篇文章,但是那篇文章更多的是在讨论"面试前该不该刷题"这个话题,而这篇文章将会更加聚焦在面试前如何准备,以及工作当中如何学习这个话

Java程序员学习一天半C++的感想

大学期间,学了一学期的C语言,当然包括学习数据结构时,用的也是C语言.当时刚刚接触计算机,对于编程更是一无所知.上课学习学习,偶尔会照着书上敲一下代码.大二下学期,就丢掉了不用了.最近由于工作的需要,要使用Java Native Interface,所以就学习了1天半的C++,对C++有了一点点的了解,写一下自己的理解. 一天半时间,也学不多少东西,我主要就搞明白了下面几个问题: 1)指针 这么多年了,还记得在C语言时,最难以理解的,应该属于指针了.还记得谭浩强的那本C语言书(书名是啥,真的忘了

Java程序员的Golang入门指南(上)

Java程序员的Golang入门指南 1.序言 Golang作为一门出身名门望族的编程语言新星,像豆瓣的Redis平台Codis.类Evernote的云笔记leanote等. 1.1 为什么要学习 如果有人说X语言比Y语言好,两方的支持者经常会激烈地争吵.如果你是某种语言老手,你就是那门语言的"传道者",下意识地会保护它.无论承认与否,你都已被困在一个隧道里,你看到的完全是局限的.<肖申克的救赎>对此有很好的注脚: [Red] These walls are funny.

当世界上只剩下一个Java程序员

公元2050年,世界上只剩下了一个Java程序员. 你可能要问了,别的人都去哪儿了?原因很简单, Java没落了. 大约在2030年左右,出现了一个叫做X的语言,它既能做系统级开发(操作系统.数据库.编译器),也能做服务器端的开发,手机端,Web端都不在话下. 更为重要的是,这个新的编程语言和人类的自然语言很接近,无论大人小孩,稍微一学,很快就可以来编程.于是排名前100的语言统统消失了, 程序员们都失业了. Java也不例外,这个昔日的霸主在留下了一堆庞大而复杂的系统以后就不见了. Java程

[转] java书籍(给Java程序猿们推荐一些值得一看的好书 + 7本免费的Java电子书和教程 )

7本免费的Java电子书和教程 1. Thinking in Java (Third Edition) 本书的作者是Bruce Eckel,它一直都是Java最畅销的免费电子书.这本书可以帮助你系统的学习Java,里面包含有很多好的代码示例.第三版仍旧是免费的,直到第四版才开始收费,不过仍旧值得买一本收藏. Think in Java 免费下载: Thinking in Java 2. The Java Tutorials 这个教程来自于Oracle/Sun.对于初学者是不错的选择.我们可以根据

十个JAVA程序员容易犯的错误&#187;

十个JAVA程序员容易犯的错误 ▉1. Array 转 ArrayList 一般开发者喜欢用: List<String> list = Arrays.asList(arr); Arrays.asList() 会返回一个ArrayList,这是Arrays里内嵌的一个私有静态类,而并不是java.util.ArrayList 类java.util.Arrays.ArrayList 有set(), get(), contains()方法,但并支持添加元素,所以大小是固定的,想要创建一个真正的Arr

Java程序员常犯的10个错误

本文总结了Java程序员常犯的10个错误. #1. 把Array转化成ArrayList 把Array转化成ArrayList,程序员经常用以下方法: List<String> list = Arrays.asList(arr); Arrays.asList() 实际上返回一个ArrayList,但是这个ArrayList是Arrays的一个内部私有类,而不是java.util.ArrayList类.这个私有类java.util.Arrays.ArrayList有set(), get(), c