如何对java链表进行增、删、查、改操作
如何对java链表进行增、删、查、改操作?针对这个问题,今天小编总结了这篇文章,希望能帮助更多想解决这个问题的朋友找到更加简单易行的办法。
链表也是一个线性的数据结构,与数组不同的是,链表在内存中的存储方式是随机存储。
下面给出涵盖链表四个操作的一个完整的例子,有几点需要注意的是:
(一)在增删改查之前,都需要对给出的下标进行边界判断;
(二)增加一个名为last的节点,可以方便在链表的尾部进行操作,省去了查找到最后一个节点的时间复杂度;
(三)在链表的内部插入元素时,我们先找到要插入位置的前一个节点prevNode,然后可以记录下prevNode的next,插入时先将prevNode的next指向要插入的节点,再将要插入的节点的next指向当前的next。这一点和C++中的操作也略有不同;
(四)删除节点时,用removedNode来记录删除节点的返回值,并且不要忘了size要减1。
操作示例如下:
public class MyLinkedList { //定义一个静态的内部类 private static class Node{ int data; Node next; Node(int data){ this.data = data; } } private Node head; private Node last;//为了方便尾部插入元素的操作 private int size;//size表示链表的实际长度 public void insert(int data, int index)throws Exception{ if(index < 0 || index > size) throw new IndexOutOfBoundsException("超出链表节点范围!"); Node insertedNode = new Node(data); if(size == 0){//插入第一个元素时元素个数为0 head = insertedNode; last = insertedNode; }else if(size == index){//在链表的末尾插入 last.next = insertedNode; last = insertedNode; }else{ Node prevNode = get(index - 1); Node nextNode = prevNode.next; prevNode.next = insertedNode; insertedNode.next = nextNode; } size++; } public void update(int data, int index) throws Exception{ if(index < 0 || index >= size) throw new IndexOutOfBoundsException("超出链表节点范围!"); if(index == 0) head.data = data; else if(index == size - 1) last.data = data; else{ Node temp = get(index); temp.data = data; } } public Node remove(int index) throws Exception { if(index < 0 || index >= size){ throw new IndexOutOfBoundsException("超出链表节点范围!"); } Node removedNode = null;//不给removedNode分配堆内存 if(index == 0){ removedNode = head; head = head.next; } else if(index == size - 1){ //删除尾结点 Node prevNode = get(index - 1); removedNode = prevNode.next; prevNode.next = null; last = prevNode; } else{ Node prevNode = get(index - 1); Node nextNode = prevNode.next.next; removedNode = prevNode.next; prevNode.next = nextNode; } size--; return removedNode; } //查找链表元素 public Node get(int index) throws Exception{ if(index < 0 || index >= size){ throw new IndexOutOfBoundsException("超出链表节点范围!"); } Node temp = head; for(int i = 0; i < index; i++){ temp = temp.next; } // size--; return temp; } //输出链表 public void output(){ Node temp = head; while(temp != null){ System.out.println(temp.data); temp = temp.next; } } public static void main(String[] args) throws Exception{ MyLinkedList myLinkedList = new MyLinkedList(); myLinkedList.insert(3,0); myLinkedList.insert(7,1); myLinkedList.insert(9,2); myLinkedList.insert(5,3); myLinkedList.insert(6,1); myLinkedList.remove(0); myLinkedList.update(2,1); myLinkedList.output(); System.out.println(myLinkedList.size); } }
关于对java链表进行增、删、查、改操作的方法就分享到这里了,希望以上内容可以对大家有一定的帮助,可以学到更多知识。如果觉得文章不错,可以把它分享出去让更多的人看到。