如何将值按升序排序单独链接列表 [英] How do I sort values into ascending order Singly Linked List

问题描述

public class ItemLinkedList {
    private ItemInfoNode head;
    private ItemInfoNode tail;
    private int size = 0;

    public int getSize() {
        return size;
    }

    public void addBack(ItemInfo info) {
        size++;
        if (head == null) {
            head = new ItemInfoNode(info, null, null);
            tail = head;
        } else {
            ItemInfoNode node = new ItemInfoNode(info, null, tail);
            this.tail.next =node;
            this.tail = node;
        }
    }

    public void addFront(ItemInfo info) {
        size++;
        if (head == null) {
            head = new ItemInfoNode(info, null, null);
            tail = head;
        } else {
            ItemInfoNode node = new ItemInfoNode(info, head, null);
            this.head.prev = node;
            this.head = node;
        }
    }

    public ItemInfo removeBack() {
        ItemInfo result = null;
        if (head != null) {
            size--;
            result = tail.info;
            if (tail.prev != null) {
                tail.prev.next = null;
                tail = tail.prev;
            } else {
                head = null;
                tail = null;
            }
        }
        return result;
    }

    public ItemInfo removeFront() {
        ItemInfo result = null;
        if (head != null) {
            size--;
            result = head.info;
            if (head.next != null) {
                head.next.prev = null;
                head = head.next;
            } else {
                head = null;
                tail = null;
            }
        }
        return result;
    }

    public class ItemInfoNode {

        private ItemInfoNode next;
        private ItemInfoNode prev;
        private ItemInfo info;

        public ItemInfoNode(ItemInfo info, ItemInfoNode next, ItemInfoNode prev) {
            this.info = info;
            this.next = next;
            this.prev = prev;
        }

        public void setInfo(ItemInfo info) {
            this.info = info;
        }

        public void setNext(ItemInfoNode node) {
            next = node;
        }

        public void setPrev(ItemInfoNode node) {
            prev = node;
        }

        public ItemInfo getInfo() {
            return info;
        }

        public ItemInfoNode getNext() {
            return next;
        }

        public ItemInfoNode getPrev() {
            return prev;
        }
    }
}

推荐答案

这是双链表...



比较你必须声明ItemInfo Comparable：

It's a double linked List...

For comparision you have to declare ItemInfo Comparable:

public class ItemInfo implements Comparable<ItemInfo> {
	@Override
	int compareTo(ItemInfo o) {
		if (this==o) return 0;
		...
	}
}

接下来在ItemLinkedList中创建一个方法：

next in ItemLinkedList create a method:

public void addSorted(ItemInfo info) {
	if (null==info) return;
	if (null==head || info.compareTo(head.getInfo())<0) {
		addFront(info);
	} else if (info.compareTo(tail.getInfo())>=0) {
		addBack(info);
	} else {
		ItemInfoNode p = head;
		ItemInfoNode prev = null;
		while (null!=p && info.compareTo(p.getInfo())<0) {
			prev = p;
			p = p.getNext();
		}
		if (null!=p) {
			// create new node
			ItemInfoNode node = new ItemInfoNode(info, p, prev);
			// insert
			if (null!=prev) {
				prev.setNext(node);
			}
			p.setPrev(node);
			++size;
		}
	}
}

这篇关于如何将值按升序排序单独链接列表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！