链表的实现和数组的实现最大的不同在于链表的插入操作代价要低于数组。只是整体代价还是数组更低,由于链表的构造和连接部分代价事实上非常高。
基本结构
- private Node head = null;
push 操作
- public void push(String str) {
- // create a new node and put the str into item
- Node newNode = new Node(str);
- // insert before the new node
- newNode.next = head;
- head = newNode;
- }
pop 操作
- public String pop() {
- String popItem; // store the pop String
- // if stack is not empty
- if (!isEmpty()) {
- popItem = head.item;
- head = head.next;
- return popItem;
- }
- // empty can not delete
- else {
- System.err.println("Stack is empty");
- return "";
- }
- }
判空
- public boolean isEmpty() {
- return head == null;
- }
求 size 的操作
- public int size() {
- int size = 0;
- while (head != null) {
- head = head.next;
- size++;
- }
- return size;
- }
来源: http://www.bubuko.com/infodetail-2029543.html