频道栏目
首页 > 程序开发 > 软件开发 > Java > 正文
Java -- 栈、队列等数据结构的简单链表实现
2016-10-09 09:42:55         来源:吾生也有涯,而知也无涯  
收藏   我要投稿

链表是一种递归的数据结构,它或者为null,或者是指向一个节点的引用,该节点含有一个泛型的元素和一个指向另一条链表的引用。在链表头部插入元素,插入的原始最后出现在链表的首部;在链表尾部插入元素,插入的元素最后出现在链表的尾部;删除链表中间部分的节点,则需要遍历链表(左向右是首到尾)。
一般在某个数据结构类的内部定义一个表示链表节点的内部类:

    private static class Node{
        private T item;
        private Node next;
    }  
背包基本实现:
/**
 * 背包是一种不支持从中删除元素的集合数据类型,它的目的就是帮助用例收集元素并迭代遍历所有收集到的元素,链表实现
 * 
 * @author xzm
 *
 * @param 
 */
public class BagMain implements Iterable { //实现Iterable接口允许我们使用增强for循环遍历元素
    /**
     * 数据域、指针域
     * @author xzm
     *
     */
    private static class Node{
         private T item; 
         private Node next;
    }
    
    private int count;
    private Node first;
    
    public BagMain() {
        first = null;
        count = 0;
    }
    
    /**
     * 表头出插入一个节点
     * @param item
     */
    public void add(T item) {
        Node oldlast = first;
        first = new Node();
        first.item = item;
        first.next = oldlast;
        count++;
    }
    public boolean isEmpty() {
        return first == null;
    }
    public int size() {
        return count;
    }
    @Override
    public Iterator iterator() {
        // TODO Auto-generated method stub
        return new BagIterator();
    }
    private class BagIterator implements Iterator {
        
        private Node current = first;
        @Override
        public boolean hasNext() {
            return current != null;
        }
        @Override
        public T next() {
            T item = current.item;
            current = current.next;
            return item;
        }
    }
}
队列基本实现:
/**
 * 先进先出队列是一种基于先进先出策略的集合模型,在表尾插入元素
 * 
 * @author xzm
 *
 */
public class QueueMain implements Iterable {
    private Node head;// 表头节点
    private Node tail;// 表尾节点
    private int count;
    private static class Node {
        private T item;
        private Node next;
    }
    public QueueMain() {
        head = null;
        tail = null;
        count = 0;
    }
    /**
     * 队列尾部添加元素
     * 
     * @param item
     */
    public void enqueue(T item) {
        Node oldlast = tail;
        tail = new Node();
        tail.item = item;
        tail.next = null;
        if (isEmpty())
            head = tail;
        else
            oldlast.next = tail;
        count++;
    }
    /**
     * 队列头部删除最早添加的元素
     * 
     * @return
     */
    public T dequeue() {
        T item = head.item;
        head = head.next;
        if (isEmpty())
            tail = null;
        count--;
        return item;
    }
    public boolean isEmpty() {
        return head == null;
    }
    public int size() {
        return count;
    }
    @Override
    public Iterator iterator() {
        return new QueueIterator();
    }
    private class QueueIterator implements Iterator {
        private Node current = head;
        @Override
        public boolean hasNext() {

            return current != null;
        }
        @Override
        public T next() {
            T item = current.item;
            current = current.next;
            return item;
        }
    }
}
栈基本实现:
/**
 * 栈是一种基于先进后出策略的集合模型,在表头插入元素
 * 
 * @author xzm
 *
 */
public class StackMain implements Iterable {
    private Node head; // 表头节点
    private int count;
    private static class Node {
        private T item;
        private Node next;
    }
    public StackMain() {
        head = null;
        count = 0;
    }
    /**
     * 表头添加一个元素
     */
    public void push(T item) {
        Node oldhead = head;
        head = new Node();
        head.item = item;
        head.next = oldhead;
        count++;
    }
    /**
     * 删除最近添加的元素
     * 
     * @return
     */
    public T pop() {
        T item = head.item;
        head = head.next;
        count--;
        return item;
    }
    public boolean isEmpty() {
        return head == null;
    }
    public int size() {
        return count;
    }
    @Override
    public Iterator iterator() {
        return new StackIterator();
    }
    private class StackIterator implements Iterator {
        private Node currnet = head;
        @Override
        public boolean hasNext() {
            return currnet != null;
        }
        @Override
        public T next() {
            T item = currnet.item;
            currnet = currnet.next;
            return item;
        }
    }
}
双向链表基本实现:
/**
 * 双向链表
 * 
 * @author xzm
 *
 * @param 
 */
public class BidirectionalLinkedListMain implements Iterable {
    private DoubleNode head;
    private DoubleNode tail;
    private int count;
    private static class DoubleNode {
        private T item;
        private DoubleNode previousNode; // 前驱节点
        private DoubleNode posteriorNode; // 后驱节点
    }
    public BidirectionalLinkedListMain() {
        head = null;
        tail = null;
        count = 0;
    }
    /**
     * 首部插入元素
     * 
     * @param item
     */
    public void insertAtHead(T item) {
        DoubleNode oldhead = head;
        head = new DoubleNode<>();
        head.item = item;
        head.posteriorNode = oldhead;
        head.previousNode = null;
        if (isEmpty()) {
            tail = head;
        } else if (oldhead != null) {
            oldhead.previousNode = head;
        }
        count++;
    }
    /**
     * 尾部插入元素
     * 
     * @param item
     */
    public void insertAtTail(T item) {
        DoubleNode oldtail = tail;
        tail = new DoubleNode<>();
        tail.item = item;
        tail.posteriorNode = null;
        tail.previousNode = oldtail;
        if (isEmpty())
            head = tail;
        else if (oldtail != null) {
            oldtail.posteriorNode = tail;
        }
        count++;
    }
    /**
     * 首部删除元素
     * 
     * @return
     * @throws NoElementException
     */
    public T delectAtHead() throws NoElementException {
        if (count <= 0)
            throw new NoElementException("链表中没有元素,首部删除失败");
        T item = head.item;
        if (size() == 1) {
            System.out.println("链表中只有一个元素");
            tail = head = null;
        } else {
            DoubleNode newhead = head.posteriorNode;
            newhead.previousNode = null;
            head.posteriorNode = null;
            head = newhead;
        }
        count--;
        return item;
    }
    /**
     * 尾部删除元素
     * 
     * @return
     * @throws NoElementException
     */
    public T delectAtTail() throws NoElementException {
        if (count <= 0)
            throw new NoElementException("链表中没有元素,尾部删除失败");
        T item = tail.item;
        if (size() == 1) {
            System.out.println("链表中只有一个元素");
            head = tail = null;
        } else {
            DoubleNode newtail = tail.previousNode;
            newtail.posteriorNode = null;
            tail.previousNode = null;
            tail = newtail;
        }
        count--;
        return item;
    }
    /**
     * 在某个节点之前插入元素,注意更新在首部插入节点时,更新head指针
     * 
     * @param data
     *            节点的值
     * 
     * @param insertItem
     *            插入的值
     * @throws NoElementException 
     */
    public boolean insertBeforeNode(T data, T insertItem) throws NoElementException {
        if (count <= 0)
            throw new NoElementException("链表中没有元素,插入失败");
        
        DoubleNode other = head;
        while (other != null) {
            if (other.item.equals(data)) {
                DoubleNode insert = new DoubleNode<>();
                insert.item = insertItem;
                insert.posteriorNode = other;
                insert.previousNode = other.previousNode;
                other.previousNode = insert;
                if (insert.previousNode != null) {
                    insert.previousNode.posteriorNode = insert;
                } else
                    head = insert;
                count++;
                return true;
            }
            other = other.posteriorNode;
        }
        System.out.println("没有找到值为" + data + "的节点,插入失败");
        return false;
    }
    /**
     * 在某个节点之前插入元素,注意在尾部插入节点时,更新tail指针
     * 
     * @param data
     *            节点的值
     * 
     * @param insertItem
     *            插入的值
     * @throws NoElementException 
     */
    public boolean insertAfterNode(T data, T insertItem) throws NoElementException {
        
        if (count <= 0)
            throw new NoElementException("链表中没有元素,插入失败");
        
        DoubleNode other = head;
        while (other != null) {
            if (other.item.equals(data)) {
                DoubleNode insert = new DoubleNode<>();
                insert.item = insertItem;
                insert.previousNode = other;
                insert.posteriorNode = other.posteriorNode;
                other.posteriorNode = insert;
                if (insert.posteriorNode != null)
                    insert.posteriorNode.previousNode = insert;
                else
                    tail = insert;
                count++;
                return true;
            }
            other = other.posteriorNode;
        }
        System.out.println("没有找到值为" + data + "的节点,插入失败");
        return false;
    }
    /**
     * 删除某个节点
     * 
     * @param data
     *            节点的值,从链表首部开始计算
     * @throws NoElementException
     */
    public boolean delectNode(int data) throws NoElementException {
        if (count <= 0)
            throw new NoElementException("链表中没有元素,无法删除元素");
        
        DoubleNode other = head;
        while (other != null) {
            if (other.item.equals(data)) {
                if(size() == 1){
                    tail = head = null;
                }else if (other.previousNode == null) {
                    DoubleNode newhead = head.posteriorNode;
                    newhead.previousNode = null;
                    other.posteriorNode = null;
                    head = newhead;
                } else if (other.posteriorNode == null) {
                    DoubleNode newtail = other.previousNode;
                    newtail.posteriorNode = null;
                    other.previousNode = null;
                    tail = newtail;
                } else {
                    other.previousNode.posteriorNode = other.posteriorNode;
                    other.posteriorNode.previousNode = other.previousNode;
                    other.previousNode = null;
                    other.posteriorNode = null;
                }
                count--;
                return true;
            }
            other = other.posteriorNode;
        }
        System.out.println("没有找到值为" + data + "的节点,删除失败");
        return false;
    }
    public boolean isEmpty() {
        return count == 0;
    }
    public int size() {
        return count;
    }
    @Override
    public Iterator iterator() {
        return new BidirectionalIterator();
    }
    private class BidirectionalIterator implements Iterator {
        private DoubleNode current = head;
        @Override
        public boolean hasNext() {
            return current != null;
        }
        @Override
        public T next() {
            T item = current.item;
            current = current.posteriorNode;
            return item;
        }
    }
} 
双向链表基本测试代码:
		BidirectionalLinkedListMain listMain = new BidirectionalLinkedListMain<>();
		
		System.out.println("首部插入1");
		listMain.insertAtHead(1);
		System.out.println("isEmpyt: " + listMain.isEmpty() + " size: " + listMain.size());
		for (Integer integer : listMain) {
			System.out.print(" " + integer);
		}
		System.out.println();
		
		System.out.println("尾部插入3");
		listMain.insertAtTail(3);
		System.out.println("isEmpyt: " + listMain.isEmpty() + " size: " + listMain.size());
		for (Integer integer : listMain) {
			System.out.print(" " + integer);
		}
		System.out.println();
		
		System.out.println("在3之后插入4");
		listMain.insertAfterNode(3, 4);
		System.out.println("isEmpyt: " + listMain.isEmpty() + " size: " + listMain.size());
		for (Integer integer : listMain) {
			System.out.print(" " + integer);
		}
		System.out.println();
		
		System.out.println("3之前插入5");
		listMain.insertBeforeNode(3,5);
		System.out.println("isEmpyt: " + listMain.isEmpty() + " size: " + listMain.size());
		for (Integer integer : listMain) {
			System.out.print(" " + integer);
		}
		System.out.println();
		
		System.out.println("删除4");
		listMain.delectNode(4);
		System.out.println("isEmpyt: " + listMain.isEmpty() + " size: " + listMain.size());
		for (Integer integer : listMain) {
			System.out.print(" " + integer);
		}
		System.out.println();
输出结果:
测试双向链表
首部插入1
isEmpyt: false size: 1
 1
尾部插入3
isEmpyt: false size: 2
 1 3
在3之后插入4
isEmpyt: false size: 3
 1 3 4
3之前插入5
isEmpyt: false size: 4
 1 5 3 4
删除4
isEmpyt: false size: 3
 1 5 3
以上。

点击复制链接 与好友分享!回本站首页
相关TAG标签 数据结构 队列
上一篇:Java中的static关键字解析
下一篇:Java数据结构与算法之常见排序算法总结
相关文章
图文推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站