Java构建四向列表前后左右都关联|极客教程

Java构建四向列表前后左右都关联

在Java中，我们可以使用四向链表（Fourway Linked List）来构建一个数据结构，其中每个节点都会与其前后左右四个方向的节点关联。这种数据结构在某些应用中非常有用，比如游戏地图搜索、像素的上下左右关联等。

在本文中，我们将详细介绍如何使用Java来实现一个四向链表，并确保每个节点都与其前后左右节点关联。

1. 节点类的设计

首先，我们需要设计一个节点类来表示四向链表中的节点。每个节点应该包含四个方向的引用，即前、后、左、右四个方向。

public class FourwayNode {
    int data;
    FourwayNode prev;
    FourwayNode next;
    FourwayNode left;
    FourwayNode right;

    public FourwayNode(int data) {
        this.data = data;
    }
}

在上面的代码中，我们定义了一个FourwayNode类，其中包含一个整型数据data以及四个方向的引用prev、next、left、right。在构造方法中，我们初始化了数据data。

2. 构建四向链表

接下来，我们需要编写一个类来表示四向链表，并包含一些操作方法来插入、删除节点等。

public class FourwayLinkedList {
    FourwayNode head;

    public FourwayLinkedList() {
        this.head = null;
    }

    public void insert(int data) {
        FourwayNode newNode = new FourwayNode(data);

        if (head == null) {
            head = newNode;
        } else {
            FourwayNode current = head;
            while (current.next != null) {
                current = current.next;
            }
            current.next = newNode;
            newNode.prev = current;
            newNode.left = current.left;
            newNode.right = current.right;
        }
    }

    public void delete(int data) {
        FourwayNode current = head;
        while (current != null) {
            if (current.data == data) {
                current.prev.next = current.next;
                current.next.prev = current.prev;
                current.left.right = current.right;
                current.right.left = current.left;
                break;
            }
            current = current.next;
        }
    }
}

在上面的代码中，我们定义了一个FourwayLinkedList类，包含一个头节点head以及insert和delete方法。在insert方法中，我们创建一个新节点并将其插入到链表的末尾，同时确保新节点与其前后左右节点都关联。在delete方法中，我们通过遍历链表找到要删除的节点，并确保其前后左右节点正确关联。

3. 测试四向链表

现在，我们来测试一下我们构建的四向链表是否正确。

public class Main {
    public static void main(String[] args) {
        FourwayLinkedList list = new FourwayLinkedList();

        list.insert(1);
        list.insert(2);
        list.insert(3);
        list.insert(4);

        list.delete(3);

        FourwayNode current = list.head;
        while (current != null) {
            System.out.print(current.data + " ");
            current = current.next;
        }
    }
}