网站开发文档百度文库,如何推广一个网站,自动翻译网站软件,design网站目录
1. 链表
2. 创建Node
3. 增加
4. 获取元素
5. 删除
6. 遍历链表
7. 查找元素是否存在
8. 链栈的实现
9. 链队的实现 1. 链表
数据存放在Node结点中 优点#xff1a;不用考虑扩容和缩容的问题#xff0c;实现了动态存储数据
缺点#xff1a;没有…目录
1. 链表
2. 创建Node
3. 增加
4. 获取元素
5. 删除
6. 遍历链表
7. 查找元素是否存在
8. 链栈的实现
9. 链队的实现 1. 链表
数据存放在Node结点中 优点不用考虑扩容和缩容的问题实现了动态存储数据
缺点没有随机访问的能力
2. 创建Node
先创建一个MyLinkedList类初始化Node结点内部类
private class Node {private T val;private Node next;public Node() {this.val null;this.next null;}public Node(T val) {this.val val;this.next null;}}
3. 增加
1 在头部添加 public void addHead(T val) {Node node new Node(val);node.next this.header;this.header node;this.size;}
2 在尾部添加 public void tail(T val) {Node node new Node(val);this.size;if(header.nextnull){this.headernode;return;}Node cur header;while (cur.next!null){cur cur.next;}cur.nextnode;}
3 在任意位置添加 public void add(int index, T val) {if (index 0 || index this.size) {throw new IllegalArgumentException(index is invalid);}//要插入的结点Node node new Node(val);//新建一个虚拟头节点Node dummyHead new Node(null);dummyHead.next header;Node pre dummyHead;//找到待插入位置的前一个结点for (int i 0; i index; i) {pre pre.next;}node.next pre.next;pre.next node;//更新头节点header dummyHead.next;this.size;}
4. 获取元素
1 获取头部元素
public T getHead() {if (isEmpty()) {return null;}return header.val;
}
2 获取尾部元素
public T getHail() {if (isEmpty()) {return null;}Node cur this.header;while (cur.next ! null) {cur cur.next;}return cur.val;}
3 获取任意节点元素
public T get(int index) {if (index 0 || index this.size) {throw new IllegalArgumentException(index is invalid);}Node cur this.header;int i 1;while (i index) {cur cur.next;i;}return cur.val;}
5. 删除
1 通过下标删除结点 public OptionalT removeByIndex(int index){if(index0||indexthis.size){return Optional.empty();}//判断是否是头结点//使用虚拟头节点Node dummyNode new Node(null);dummyNode.next header;Node pre dummyNode;int i1;//寻找要删除的结点while(iindex){pre pre.next;i;}//改变指针指向Node delNode pre.next;pre.next delNode.next;delNode.next null;this.size--;this.header dummyNode.next;return Optional.of(delNode.val);}
2 通过值删除结点
public void removeByVal(T val){if(isEmpty()){return;}Node dummyNode new Node(null);dummyNode.next header;Node pre dummyNode;while(pre.next!null){Node cur pre.next;if(cur.val.equals(val)){pre.nextcur.next;cur.nextnull;size--;}else {pre pre.next;}}header dummyNode.next;}
3 不使用虚拟头结点删除元素
public void removeWithoutDummyHead(T val){while(this.header!nullthis.header.val.equals(val)){this.header this.header.next;this.size--;}if(this.headernull){return;}//此时头节点一定不是要删除的结点Node pre this.header;while(pre.next!null){if(pre.next.val.equals(val)){pre.next pre.next.next;this.size--;}else{pre pre.next;}}
}
6. 遍历链表
重写toString()方法将他拼接成链表的样子
Overridepublic String toString() {//创建一个临时结点Node cru header;StringBuffer sb new StringBuffer();while (cru ! null) {sb.append(cru.val ---);cru cru.next;}sb.append(Null);return sb.toString();}
7. 查找元素是否存在
public boolean contains(T val) {Node res new Node(val);Node cur header;for (int i 0; i this.size; i) {if (res.val.equals(cur.val)) {return true;}cur cur.next;}return false;}
8. 链栈的实现
public interface StackT {void push(T element);T pop();int getSize();boolean isEmpty();T peek();
}
public class LinkedStackT implements StackT {private MyLinkedListT data;public LinkedStack(MyLinkedListT data) {this.data data;}Overridepublic void push(T element) {this.data.addTail(element);}Overridepublic T pop() {OptionalT optional this.data.removeByIndex(0);if(optional.isPresent()){return optional.get();}return null;}Overridepublic int getSize() {return this.data.getSize();}Overridepublic boolean isEmpty() {return this.data.isEmpty();}Overridepublic T peek() {return this.data.getHead();}
}
9. 链队的实现
public interface QueueT{void offer(T ele);T poll();boolean isEmpty();int getSize();T getFront();
}
public class LinkedQueue implements Queue {private MyLinkedList data;public LinkedQueue(MyLinkedList myLinkedList) {this.data myLinkedList;}Overridepublic void offer(Object ele) {this.data.addTail(ele);}Overridepublic Object poll() {return this.data.removeByIndex(0);}Overridepublic boolean isEmpty() {return this.data.isEmpty();}Overridepublic int getSize() {return this.data.getSize();}Overridepublic Object getFront() {return this.data.getHead();}
}
