如何将单链接列表更改为双链接列表? [英] How do I change a singly-linked list to a doubly-linked list?

查看:140
本文介绍了如何将单链接列表更改为双链接列表?的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!

问题描述

我目前正在上一门Java课,这位教授告诉我们,了解链接的一种好习惯是制作一个双向链接列表。我已经创建了一个单链列表,但是在将其转换为双链列表时遇到了麻烦。所以我想知道是否有人可以给我一些建议,以确保我的最后一个电话号码与上一个电话号码相连?并且如果前面的数字和最后一个数字连接为null。这是代码的一部分,如果您想要更多,请问一下,我将发布。

I'm currently taking a Java class and the professor told us that a good practice to understand links would be to make a doubly linked list. I have made a singly linked list but I am having trouble converting it to a doubly linked list. So I was wondering if anybody could give me any suggestions on making sure my last number is connected to the previous one? And if the front number and last number connected to the null. Here is part of the code, if you wish for more of it just ask and I shall post.

用于添加元素等的代码。这是我尝试使结尾的尾部连接到最后一个数字的尝试。

The code for adding elements and such. This is my attempt of trying to make the tail which is the end connect to the last number.

public void add(int element){

            Node n = new Node();
            n.setItem(element);
            n.setNext(head);
            head = n;
            >
            //The tail connected to the new number added.
            n.setItem(element);
            n.setBefore(tail);
            tail = n;

下面的代码是insert函数,我需要确保新插入的块可以连接,但是我

The code below is the insert function which I need to make sure the new inserted blocks connect but I'm having troubles thinking of a way to make it connect for both.

public void insert(int element, int position){

        int currentposition = 0;
        Node currentNode = head;

        //Traverse to the right position
        while(currentposition < position-1){

            currentposition++;
        } 
        Node n = new Node();
        n.setItem(element);
        n.setNext(currentNode.getNext());
        currentNode.setNext(n);

        //The previous number connecting to the new number
        currentNode = tail;

    }


推荐答案

链表,您需要在类中同时添加head和tail字段,以便维护双链数据结构。

For doubly linked list, you need to add both head and tail fields in the class so that it maintains a doubly linked data structure.

private Node<T> head = null;
private Node<T> tail = head;
private int size = 0;

要将新节点添加到链接列表的末尾,可以执行

To add a new node to the end of the linked list, you can do

public void add(T element) {
    Node<T> node = new Node<T>(element);
    Node<T> current = head;
    if(current == null) {
        current = node;
        head = tail = current;
    } else {
        tail.next = node;
        node.prev = tail;
        tail = node;
    }
    size++;
}

请注意,您还需要处理第一个空列表情况if子句。添加节点时,还可以设置尾部的下一个和上一个引用。

Note that you also need to deal with the empty list case which is the first if clause. Also you can set next and prev references for tail when you add the node.

要将节点插入列表中的某个位置,您需要考虑指定的位置小于0或大于现有列表大小,则会发生错误,因为您不能插入索引超出范围的元素。这样就可以抛出异常。另外,当插入位置位于 0 head )或大小(尾巴)。考虑到所有这些情况,解决方案是:

To insert a node to the list at a certain position, you need to consider that if the specified position is less than 0 or great than the existing list size, then error occurs because you can't insert element with out of bound index. So you can throw exception. Also you need to separate the case when the inserted position is at 0 (head) or at size (tail). Considering all these cases, the solution is:

public void insert(T a, int position) {
    if (position < 0 || position > size)
        throw new IndexOutOfBoundsException();
    Node<T> node = new Node<T>(a);
    Node<T> temp;
    if(position == 0) {
        if(head == null)
            add(a);
        else {
            temp = head;
            head = node;
            node.next = temp;
            temp.prev = node;
        }
        return;
    } else if (position == size) {
        temp = tail;
        tail = node;
        temp.next = tail;
        tail.prev = temp;
        return;
    }

    Node<T> current = head;
    int i = 0;
    while (current != null && i < position-1) {
        current = current.next;
        i++;
    }

    temp = current.next;
    current.next = node;
    node.prev = current;
    node.next = temp;
    temp.prev = node;
}

这篇关于如何将单链接列表更改为双链接列表?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!

查看全文
登录 关闭
扫码关注1秒登录
发送“验证码”获取 | 15天全站免登陆