有序链表的基本用法

客官°小女子只卖身不卖艺 2022-05-18 06:00 153阅读 0赞

**有序链表：**链表本身是一种无序的数据结构，元素的插入和删除不能保证顺序性，但是有没有有序的链表呢？答案是肯定的，我们在单链表中插入元素时，只需要将插入的元素与头结点及其后面的结点比较，从而找到合适的位置插入即可。一般在大多数需要使用有序数组的场合也可以使用有序链表，有序链表在插入时因为不需要移动元素，因此插入速度比数组快很多，另外链表可以扩展到全部有效的使用内存，而数组只能局限于一个固定的大小中。

有序链表的Java代码实现：

package parking;
    
    import java.util.Random;
    
    class Node {
    
    	Integer data;
    	Node next;
    
    	public Node(Integer data) {
    		this.data = data;
    	}
    
    }
    
    public class LinkOrder {
    
    	private Node head;
    	private int size;
    
    	public LinkOrder() {
    		this.head = null;
    		this.size = 0;
    	}
    
    	// 判断是否为空
    	private boolean isEmpty() {
    		return head == null ? true : false;
    	}
    
    	// 获取链表大小
    	private int getSize() {
    		return size;
    	}
    
    	// 在链表中插入一个结点，保持链表有序性（头结点最小，尾结点最大）
    	public void insert(int key) {
    		Node newLink = new Node(key);
    		Node previous = null;
    		Node current = head;
    		while (current != null && key > current.data) { // 找下个节点
    			previous = current;
    			current = current.next;
    		}
    		// 比当前节点值小，刚好插入当前节点前面
    		if (previous == null) {// 链表是空的
    			head = newLink;
    		} else {
    			previous.next = newLink;
    		}
    		newLink.next = current;
    		size++;
    	}
    
    	// 返回头结点
    	private Integer headNode() {
    		if (head == null) {
    			return null;
    		}
    		Integer value = head.data;
    		return value;
    	}
    
    	// 删除头结点，并删除
    	private Integer deleteHnode() {
    		if (head == null) {
    			return null;
    		}
    		Integer value = head.data;
    		if (head.next == null) {
    			head = null;
    		} else {
    			head = head.next;
    		}
    		size--;
    		return value;
    	}
    
    	// 删除指定结点
    	private void deleteNode(Node node) {
    		if (head == null) {
    			System.out.println("链表为空");
    			return;
    		}
    
    		Node current = head;
    		Node pre = null;
    		while (current.data != node.data) {
    			if (current.next == null) {
    				System.out.println("没有找到该结点");
    				return;
    			}
    			pre = current;
    			current = current.next;
    		}
    		if (current == head) {
    			deleteHnode();
    		} else {
    			pre.next = current.next;
    			size--;
    		}
    	}
    
    	// 遍历有序链表
    	private void sysNode() {
    		if (head == null) {
    			System.out.println("该链表为空");
    		}
    		Node current = head;
    		while (current != null) {
    			System.out.print(current.data + "-->");
    			current = current.next;
    		}
    		System.out.println();
    	}
    
    	public static void main(String[] args) {
    		// TODO Auto-generated method stub
    		LinkOrder order = new LinkOrder();
    		int i;
    		Node node;
    		for (i = 0; i < 5; i++) {
    			order.insert(new Random().nextInt(100));
    		}
    		System.out.println("有序链表大小：" + order.getSize());
    		order.sysNode();
    		System.out.println("有序链表头结点：" + order.deleteHnode());
    		order.sysNode();
    		node = new Node(new Random().nextInt(100));
    		System.out.println("删除指定结点：" + node.data);
    		order.deleteNode(node);
    		order.sysNode();
    
    	}
    
    }

效果：

有序链表大小：5
    44-->44-->59-->70-->71-->
    有序链表头结点：44
    44-->59-->70-->71-->
    删除指定结点：59
    44-->70-->71-->

### 我的座右铭：不会，我可以学；落后，我可以追赶；跌倒，我可以站起来；我一定行。 ###