链表也是一个线性的数据结构,与数组差别的是,链表在内存中的存储体式格局是随机存储。
下面给出涵盖链表四个操纵的一个完全的例子,有几点须要注重的是:
(一)在增编削查之前,都须要对给出的下标举行边境推断;
(二)增添一个名为last的节点,能够轻易在链表的尾部举行操纵,省去了查找到最后一个节点的时候复杂度;
(三)在链表的内部插进去元素时,我们先找到要插进去位置的前一个节点prevNode,然后能够纪录下prevNode的next,插进去时先将prevNode的next指向要插进去的节点,再将要插进去的节点的next指向当前的next。这一点和C++中的操纵也略有差别;
(四)删除节点时,用removedNode来纪录删除节点的返回值,而且不要忘了size要减1。
相干免费视频教程引荐:java免费视频教程
操纵示例以下:
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开发入门
以上就是怎样完成java链表中的基础操纵(增、删、查、改)的细致内容,更多请关注ki4网别的相干文章!