数据结构---链表(java)

目录

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.next==null){this.header=node;return;}Node cur = header;while (cur.next!=null){cur = cur.next;}cur.next=node;}

<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 Optional<T> removeByIndex(int index){if(index<0||index>=this.size){return Optional.empty();}//判断是否是头结点//使用虚拟头节点Node dummyNode = new Node(null);dummyNode.next = header;Node pre = dummyNode;int i=1;//寻找要删除的结点while(i<=index){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.next=cur.next;cur.next=null;size--;}else {pre = pre.next;}}header = dummyNode.next;}

<3> 不使用虚拟头结点删除元素

public void removeWithoutDummyHead(T val){while(this.header!=null&&this.header.val.equals(val)){this.header = this.header.next;this.size--;}if(this.header==null){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 Stack<T> {void push(T element);T pop();int getSize();boolean isEmpty();T peek();
}

public class LinkedStack<T> implements Stack<T> {private MyLinkedList<T> data;public LinkedStack(MyLinkedList<T> data) {this.data = data;}@Overridepublic void push(T element) {this.data.addTail(element);}@Overridepublic T pop() {Optional<T> 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 Queue<T>{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();}
}