0

我试图在java使用一个Node类时实现一个链表，并且只保留一个指向链表开头的链接（让我们称之为“第一个”）。

我需要处理2个案例-

1.当链表为空时-在这种情况下，我需要在“首先”创建一个新节点

2.当链表中有节点时

我尝试将其编码如下..但我想知道这是否是标准方式..处理第一种情况的代码块看起来有点难看..

执行此操作的标准方法是什么？

public class MyLList<Item>{
    Node first;

    public  void insertAtBeginning(Item item){
        Node old = first;
        first = new Node();
        first.item = item;
        first.next = old;
    }

    public void insertAtEnd(Item item){
        Node t = first;
        while(t!=null && t.next!=null){
            t=t.next;
        }

        if(t==null){
            first = new Node();
            first.item = item;
            return;
        }
        Node old = t;
        t = new Node();
        t.item = item;
        old.next = t;
    }

    public void traverse(){
        for(Node x=first;x!=null;x=x.next){
            System.out.print(x.item+" ");
        }
    }

    private class Node{
        Item item;
        Node next;
    }


    public static void main(String[] args) {
        MyLList<String> ll = new MyLList<String>();

        ll.insertAtEnd("X");
        ll.insertAtBeginning("B");
        ll.insertAtEnd("Y");
        ll.traverse();

    }

}
4

3 回答 3

2

您可以将其更改为更清晰：

public void insertAtEnd(Item item){
    if (first == null)
        insertAtBeginning(Item item);
    else{
        Node t = first;
        while(t!=null && t.next!=null){
            t=t.next;
        }

        Node old = t;
        t = new Node();
        t.item = item;
        old.next = t;
    }        
}
于 2013-07-30T12:14:56.813 回答
2

创建一个代表链表根的空节点，这将消除对“根为空”情况的特殊处理的需要。

像这样的东西：

    static void Main(String[] args)
    {
        MyLList<String> ll = new MyLList<String>();

        ll.insertAtEnd("X");
        ll.insertAtBeginning("B");
        ll.insertAtEnd("Y");
        ll.Traverse();

    }

    public class MyLList<Item>
    {
        Node first = new Node();

        public void insertAtBeginning(Item item)
        {
            Node oldFirst = first.next;

            first.next = new Node();
            first.next.item = item;
            first.next.next = oldFirst;
        }

        public void insertAtEnd(Item item)
        {
            Node tail = first;
            while (tail.next != null)
            {
                tail = tail.next;
            }

            tail.next = new Node();
            tail.next.item = item;
        }

        public void traverse()
        {
            for (Node x = first.next; x != null; x = x.next)
            {
                Console.Out.WriteLine(x.item + " ");
            }
        }

        private class Node
        {
            public Item item;
            public Node next;
        }



    }
于 2013-07-30T12:10:22.987 回答
0 
Linked List Program with following functionalities

1. Insert at Begining

2. Insert at End

3. Insert at any position

4. Delete at Position

5. Get Size

6. Display

7. Empty Status

8. Replace data at given position

9. Get Element by Position

10. Search Element Recursively

11. Swap only data not node

12. Swap node for given data

13. Reverse the list

14. Find Middle Element

15. Count Occurrence of a Number








    import java.util.NoSuchElementException;
    import java.util.Scanner;

    class Node<T> {

        Node<T> next = null;
        T data;

        Node(T data) {
            this.data = data;
            this.next = null;
        }
    }

    class LinkedList<T> {

        Node<T> head = null;
        Node<T> last = null;

        public LinkedList() {
            head = null;
            last = null;
        }

        public void insertAtFirst(T data) {
            Node<T> nptr = new Node<T>(data);
            if (head == null) {
                head = nptr;
                last = head;
            } else {
                nptr.next = head;
                head = nptr;
            }
            display(head);
        }

        public void insertAtLast(T data) {
            Node<T> nptr = new Node<T>(data);
            if (empty()) {
                head = nptr;
                last = nptr;
            } else {
                last.next = nptr;
                last = nptr;
            }
            display(head);
        }

        public void insertAtPosition(int position, T data) {
            if (empty()) {
                insertAtFirst(data);
                return;
            }

            Node<T> headPtr = head;
            position -= 1;
            for (int i = 1; i < size(); i++) {
                if (position == i) {
                    Node<T> nptr = new Node<T>(data);
                    Node<T> temp = headPtr.next;
                    headPtr.next = nptr;
                    nptr.next = temp;
                    break;
                }
                headPtr = headPtr.next;
            }
            display(head);
        }

        public void delete(int position) {
            if (empty())
                throw new NoSuchElementException("List is Empty!");

            if (position == 1) {
                if (head.next == null) {
                    head = null;
                } else {
                    Node<T> temp = head.next;
                    head = temp;
                }
                display(head);
                return;
            }

            if (position == size()) {
                Node<T> headPtr = head;
                Node<T> lastPtr = headPtr;
                while (headPtr.next != null) {
                    lastPtr = headPtr;
                    headPtr = headPtr.next;
                }
                lastPtr.next = null;
                last = lastPtr;
                display(head);
                return;
            }

            Node<T> startPtr = head;
            position -= 1;
            for (int i = 1; i < size(); i++) {
                if (i == position) {
                    Node<T> temp = startPtr.next;
                    temp = temp.next;
                    startPtr.next = temp;
                }
                startPtr = startPtr.next;
            }
            display(head);
        }

        public void display(Node<T> link) {
            if (link != null) {
                System.out.print(link.data + " ");
                display(link.next);
            }
        }

        public int size() {
            if (empty())
                throw new NoSuchElementException("List is Empty");

            Node<T> headPtr = head;
            int count = 1;
            while (headPtr.next != null) {
                count++;
                headPtr = headPtr.next;
            }
            return count;
        }

        public void replace(int position, T data) {
            if (empty())
                throw new NoSuchElementException("List is Empty!");

            Node<T> startPtr = head;
            for (int i = 1; i < size(); i++) {
                if (i == position) {
                    startPtr.data = data;
                    break;
                }
                startPtr = startPtr.next;
            }
            display(head);
        }

        public T elementByPosition(int position, Node<T> link, int count) {
            if (count == position) {
                return link.data;
            }
            return elementByPosition(position, link.next, ++count);
        }

        public int searchElement(T data, Node<T> link, int position) {
            if (empty())
                throw new NoSuchElementException("List is Empty!");

            if (link.data == data)
                return position;

            return searchElement(data, link.next, ++position);
        }

        public Node<T> getLinkByData(T data, Node<T> link) {
            if (link == null)
                return link;

            if (link.data == data)
                return link;

            return getLinkByData(data, link.next);
        }

        public void swapData(T firstData, T secondData) {
            if (empty())
                throw new NoSuchElementException("List is Empty!");

            Node<T> firstDataLink = getLinkByData(firstData, head);
            Node<T> secondDataLink = getLinkByData(secondData, head);
            if (firstDataLink == null || secondDataLink == null) {
                throw new NoSuchElementException("Eithe " + firstData + " or " + secondData + " not in the list");
            }
            firstDataLink.data = secondData;
            secondDataLink.data = firstData;
            display(head);
        }

        public void swapNode(T firstData, T secondData) {

            if (empty())
                throw new NoSuchElementException("List is Empty!");

            if (firstData == secondData)
                throw new NoSuchElementException("Can't swap for identical data");

            boolean foundFirstData = false;
            boolean foundSecondData = false;

            Node<T> firstDataPtr = head;
            Node<T> prevFirstDataPtr = head;
            while (firstDataPtr.next != null && !(firstDataPtr.data == firstData)) {
                prevFirstDataPtr = firstDataPtr;
                firstDataPtr = firstDataPtr.next;
            }
            if (firstDataPtr.data == firstData)
                foundFirstData = true;

            Node<T> secondDataPtr = head;
            Node<T> prevSecondDataPtr = head;
            while (secondDataPtr.next != null && !(secondDataPtr.data == secondData)) {
                prevSecondDataPtr = secondDataPtr;
                secondDataPtr = secondDataPtr.next;
            }
            if (secondDataPtr.data == secondData)
                foundSecondData = true;

            if (foundFirstData && foundSecondData) {

                // if data belongs to start or last node
                if (firstDataPtr == head)
                    head = secondDataPtr;
                else if (secondDataPtr == head)
                    head = firstDataPtr;

                if (firstDataPtr == last)
                    last = secondDataPtr;
                else if (secondDataPtr == last)
                    last = firstDataPtr;

                Node<T> nextFirstDataPtr = firstDataPtr.next;
                Node<T> nextSecondDataPtr = secondDataPtr.next;

                prevFirstDataPtr.next = secondDataPtr;
                secondDataPtr.next = nextFirstDataPtr;

                prevSecondDataPtr.next = firstDataPtr;
                firstDataPtr.next = nextSecondDataPtr;

                // if items belongs to adjacent node
                if (prevSecondDataPtr == firstDataPtr)
                    secondDataPtr.next = firstDataPtr;
                else if (prevFirstDataPtr == secondDataPtr)
                    firstDataPtr.next = secondDataPtr;

                display(head);

            } else
                throw new NoSuchElementException("Either " + firstData + " or " + secondData + " not in the list!");
        }

        public Node<T> reverse(Node<T> link) {
            if (link == null)
                return null;

            if (link.next == null)
                return link;

            Node<T> secondElement = link.next;
            link.next = null;
            Node<T> reverseRest = reverse(secondElement);
            secondElement.next = link;
            return reverseRest;
        }

        public void setHeadandLastLink() {
            Node<T> temp = head;
            head = last;
            last = temp;
            display(head);
        }

        public T middle() {
            if (empty())
                throw new NoSuchElementException("List is empty!");

            Node<T> slowPtr = head;
            Node<T> fastPtr = head;
            while (fastPtr != null && fastPtr.next != null) {
                slowPtr = slowPtr.next;
                fastPtr = fastPtr.next.next;
            }
            return slowPtr.data;
        }

        public int getOccurence(T data, int occurence, Node<T> link) {

            if (empty())
                throw new NoSuchElementException("List is Empty!");

            if (link == null)
                return occurence;

            if (link.data == data) {
                ++occurence;
            }

            return getOccurence(data, occurence, link.next);
        }

        public boolean empty() {
            return head == null;
        }

    }

    public class LinkedListTest {

        @SuppressWarnings("resource")
        public static void main(String[] args) {
            System.out.println("Welcome to Singly Linked List");
            LinkedList<Integer> linkedList = new LinkedList<Integer>();
            boolean yes = true;
            do {
                System.out.println("\n1. Insert at Begining");
                System.out.println("2. Insert at End");
                System.out.println("3. Insert at any position");
                System.out.println("4. Delete at Position");
                System.out.println("5. Get Size");
                System.out.println("6. Display");
                System.out.println("7. Empty Status ");
                System.out.println("8. Replace data at given position");
                System.out.println("9. Get Element by Position");
                System.out.println("10. Search Element Recursively");
                System.out.println("11. Swap only data not node");
                System.out.println("12. Swap node for given data");
                System.out.println("13. Reverse the list");
                System.out.println("14. Find Middle Element");
                System.out.println("15. Count Occurence of a Number");
                Scanner scanner = new Scanner(System.in);
                int choice = scanner.nextInt();
                switch (choice) {
                case 1:
                    try {
                        linkedList.insertAtFirst(scanner.nextInt());
                    } catch (Exception e) {
                        System.out.println(e.getMessage());
                    }
                    break;

                case 2:
                    try {
                        linkedList.insertAtLast(scanner.nextInt());
                    } catch (Exception e) {
                        System.out.println(e.getMessage());
                    }
                    break;

                case 3:
                    try {
                        System.out.println("Enter position");
                        int position = scanner.nextInt();
                        if (position < 1 || position > linkedList.size()) {
                            System.out.println("Invalid Position!");
                            break;
                        }
                        linkedList.insertAtPosition(position, scanner.nextInt());
                    } catch (Exception e) {
                        System.out.println(e.getMessage());
                    }
                    break;

                case 4:
                    try {
                        int position = scanner.nextInt();
                        if (position < 1 || position > linkedList.size()) {
                            System.out.println("Invalid position !");
                            break;
                        }
                        linkedList.delete(position);
                    } catch (Exception e) {
                        System.out.println(e.getMessage());
                    }
                    break;

                case 5:
                    try {
                        System.out.println(linkedList.size());
                    } catch (Exception e) {
                        System.out.println(e.getMessage());
                    }
                    break;

                case 6:
                    try {
                        linkedList.display(linkedList.head);
                    } catch (Exception e) {
                        System.out.println(e.getMessage());
                    }
                    break;

                case 7:
                    try {
                        System.out.println(linkedList.empty());
                    } catch (Exception e) {
                        System.out.println(e.getMessage());
                    }
                    break;

                case 8:
                    try {
                        System.out.println("Enter position : ");
                        int position = scanner.nextInt();
                        if (position < 1 || position > linkedList.size()) {
                            System.out.println("Invalid Position!");
                            break;
                        }
                        linkedList.replace(position, scanner.nextInt());
                    } catch (Exception e) {
                        System.out.println(e.getMessage());
                    }
                    break;

                case 9:
                    try {
                        System.out.println("Enter Position : ");
                        int position = scanner.nextInt();
                        if (position < 1 || position > linkedList.size()) {
                            System.out.println("Invalid Position !");
                            break;
                        }
                        System.out.println(linkedList.elementByPosition(position, linkedList.head, 1));
                    } catch (Exception e) {
                        System.out.println(e.getMessage());
                    }
                    break;

                case 10:
                    try {
                        System.out.println("Enter the item to Find it's position : ");
                        int data = scanner.nextInt();
                        System.out.println(linkedList.searchElement(data, linkedList.head, 1));
                    } catch (Exception e) {
                        System.out.println(e.getMessage());
                    }
                    break;

                case 11:
                    try {
                        System.out.println("Enter the items to swap");
                        int firstData = scanner.nextInt();
                        int secondData = scanner.nextInt();
                        linkedList.swapData(firstData, secondData);
                    } catch (Exception e) {
                        System.out.println(e.getMessage());
                    }
                    break;

                case 12:
                    try {
                        System.out.println("Enter the Data to swap Node");
                        int firstData = scanner.nextInt();
                        int secondData = scanner.nextInt();
                        linkedList.swapNode(firstData, secondData);
                    } catch (Exception e) {
                        System.out.println(e.getMessage());
                    }
                    break;

                case 13:
                    try {
                        linkedList.reverse(linkedList.head);
                        linkedList.setHeadandLastLink();
                    } catch (Exception e) {
                        System.out.println(e.getMessage());
                    }
                    break;

                case 14:
                    try {
                        System.out.println("Middle Element is : " + linkedList.middle());
                    } catch (Exception e) {
                        System.out.println(e.getMessage());
                    }
                    break;

                case 15:
                    try {
                        System.out.println("Enter the item to get Occurence");
                        int data = scanner.nextInt();
                        System.out.println("Occurence is : " + linkedList.getOccurence(data, 0, linkedList.head));
                    } catch (Exception e) {
                        System.out.println(e.getMessage());
                    }
                    break;

                default:
                    break;
                }
            } while (yes);
        }
    }
于 2018-06-07T05:54:16.963 回答