- 单链表(SingleLinkedList)
- 带头单链表(LinkedListWithHead)
- 双向链表
- 测试
- 带头单链表测试
- 双向链表测试
链表就像是拼火车厢
package seqlist;
public class SingleLinkedList {
private Node head;
private int size;
public void add(int val) {
Node newNode = new Node();
newNode.val = val;
// if (head == null) {
// head = newNode;
// } else {
// newNode.next = head;
// head = newNode;
// }
if (head != null) {
newNode.next = head;
}
head = newNode;
size++;
}
public void add(int index, int val) {
if (index < 0 || index > size) {
System.out.println("add index illegal!");
return;
}
if (index == 0) {
add(val);
} else {
Node newNode = new Node();
newNode.val = val;
Node prev = head;
for (int i = 0; i < index - 1; i++) {
prev = prev.next;
}
newNode.next = prev.next;
prev.next = newNode;
size++;
}
}
public void addLast(int val) {
add(size, val);
}
public int getIndexByValue(int val) {
int index = 0;
for (Node x = head; x != null; x = x.next) {
if (x.val == val) {
return index;
}
index++;
}
return -1;
}
public boolean isContains(int val) {
// for (Node x = head; x != null; x = x.next) {
// if(x.val == val){
// return true;
// }
// }
// return false;
return getIndexByValue(val) != -1;
}
public int getValueByIndex(int index) {
Node node = head;
if (isIndexLegal(index)) {
for (int i = 0; i < index; i++) {
node = node.next;
}
return node.val;
}
System.out.println("index illegal!!!");
return -1;
}
public int set(int index, int newVal) {
if (isIndexLegal(index)) {
Node x = head;
for (int i = 0; i < index; i++) {
x = x.next;
}
int oldVal = x.val;
x.val = newVal;
return oldVal;
}
System.out.println("index illegal!!!");
return -1;
}
public int removeValueByIndex(int index) {
if (isIndexLegal(index)) {
if (index == 0) {
Node node = head;
head = head.next;
node.next = null;
size--;
return node.val;
}
Node prev = head;
for (int i = 0; i < index - 1; i++) {
prev = prev.next;
}
Node node = prev.next;
prev.next = node.next;
node.next = null;
size--;
return node.val;
}
System.out.println("index illegal!!!");
return -1;
}
public void removeValueOnce(int val) {
// int index = 0;
// for (Node x = head; x != null; x = x.next) {
// if(x.val == val){
// removeValueByIndex(index);
// return;
// }
// index++;
// }
Node prev = head;
if (head == null) {
System.out.println("LinkedList is empty!");
// return;
} else if (head.val == val) {
Node x = head;
head = head.next;
x.next = null;
size--;
} else {
for (Node node = head; node.next != null; node = node.next) {
if (node.next.val == val) {
Node delete = node.next;
node.next = delete.next;
delete.next = null;
size--;
return;
}
}
}
}
public void removeAllValue(int val) {
while (head != null && head.val == val) {//这两个条件的位置一定不能换！！！
Node x = head;
head = head.next;
x.next = null;
size--;
}
if (head == null) {
return;
}
Node node = head;
while (node.next != null) {
if (node.next.val == val) {
Node delete = node.next;
node.next = delete.next;
delete.next = null;
size--;
} else {
node = node.next;
}
}
}
public int removeFirst() {
return removeValueByIndex(0);
}
public int removeLast() {
return removeValueByIndex(size - 1);
}
private boolean isIndexLegal(int index) {
// if (index < 0 || index >= size) {
// return false;
// }
// return true;
return !(index < 0 || index >= size);
}
public String toString() {
String ret = "";
// Node x = head;
// while (x != null) {
// ret += x.val;
// ret += "->";
// x = x.next;
// }
for (Node x = head; x != null; x = x.next) {
ret += x.val;
ret += "->";
}
ret += "NULL";
return ret;
}
public static void main(String[] args) {
SingleLinkedList singleLinkedList = new SingleLinkedList();
singleLinkedList.add(1);
singleLinkedList.add(1);
singleLinkedList.add(1);
singleLinkedList.add(1);
singleLinkedList.add(1);
singleLinkedList.add(1);
singleLinkedList.add(1);
// singleLinkedList.add(0, 6);
// singleLinkedList.add(singleLinkedList.size, 6);
// singleLinkedList.addLast(7);
// singleLinkedList.set(12, 6);
// singleLinkedList.removeValueByIndex(0);
// singleLinkedList.removeValueOnce(6);
singleLinkedList.removeAllValue(1);
// singleLinkedList.removeFirst();
// singleLinkedList.removeLast();
// System.out.println(singleLinkedList.getIndexByValue(6));
// System.out.println(singleLinkedList.isContains(4));
// System.out.println(singleLinkedList.isContains(8));
// System.out.println(singleLinkedList.getValueByIndex(1));
System.out.println(singleLinkedList);
}
}
class Node {
int val;
Node next;
public Node() {
}
public Node(int val) {
this.val = val;
}
public Node(int val, Node next) {
this.val = val;
this.next = next;
}
}
带头单链表(LinkedListWithHead)
package seqlist;
public class LinkedListWithHead {
private int size; // 当前链表中有效数据的个数(不包含头节点)
// 实实在在存在的Node对象，不存储数据，就作为火车头
private Node dummyHead = new Node();
public void addFirst(int val) {
// 1
// Node node = new Node();
// node.val = val;
// node.next = dummyHead.next;
// dummyHead.next = node;
// 2
// Node node = new Node(val,dummyHead.next);
// dummyHead.next = node;
// 3
dummyHead.next = new Node(val, dummyHead.next);
size++;
}
public void add(int index, int val) {
if (index < 0 || index > size) {
System.err.println("add index illegal!");
return;
}
Node prev = dummyHead;
for (int i = 0; i < index; i++) {
prev = prev.next;
}
// 此时prev引用就是待插入位置的前驱
// 1.
// Node node = new Node();
// node.val = val;
// node.next = prev.next;
// prev.next = node;
// 2.使用构造方法在产生新节点的同时给node赋值以及链接后继节点
// Node node = new Node(val,prev.next);
// prev.next = node;
// 3.使用匿名对象
prev.next = new Node(val, prev.next);
size++;
}
public int remove(int index) {
// 1.索引合法性
if (rangeCheck(index)) {
Node prev = dummyHead;
for (int i = 0; i < index; i++) {
prev = prev.next;
}
Node cur = prev.next;
prev.next = cur.next;
int val = cur.val;
cur.next = cur = null;
size--;
return val;
}
System.err.println("index illegal!");
return -1;
}
public void removeAllValue(int val) {
Node prev = dummyHead;
while (prev.next != null) {
if (prev.next.val == val) {
prev.next = prev.next.next;
size--;
} else {
prev = prev.next;
}
}
}
private boolean rangeCheck(int index) {
if (index < 0 || index >= size) {
return false;
}
return true;
}
public String toString() {
String ret = "";
for (Node x = dummyHead.next; x != null; x = x.next) {
ret += x.val;
ret += "->";
}
ret += "NULL";
return ret;
}
}
双向链表
package seqlist;
import com.sun.imageio.plugins.jpeg.JPEGImageReaderResources;
import jdk.nashorn.internal.codegen.DumpBytecode;
import seqlist.leetcode.ListNode;
import java.util.Optional;
public class DoubleLinkedList {
private int size;//有效节点个数
private DoubleNode head;//当前头节点
private DoubleNode tail;//当前尾结点
//头插
public void addFirst(int val) {
//首先创建一个新节点
// DoubleNode node = new DoubleNode(val);
DoubleNode node = new DoubleNode(null, val, head);
if (tail == null) {
tail = node;
} else {
// node.next = head;
head.prev = node;
}
head = node;
size++;
}
//尾插
public void addLast(int val) {
//这个节点就是插入后的尾结点
DoubleNode node = new DoubleNode(tail, val, null);
if (tail == null) {
head = node;
} else {
tail.next = node;
}
tail = node;
size++;
}
public void add(int index, int val) {
if (index < 0 || index > size) {
System.out.println("add index illegal!");
return;
}
if (index == 0) addFirst(val);
else if (index == size) addLast(val);
else {
// DoubleNode prev = node(index-1);
// DoubleNode node = new DoubleNode(prev,val,prev.next);
// prev.next.prev = node;
// prev.next = node;
// size++;
DoubleNode prev = node(index - 1);
DoubleNode next = prev.next;
DoubleNode cur = new DoubleNode(prev, val, next);
prev.next = cur;
next.prev = cur;
size++;
}
}
public int getValueByIndex(int index) {
if (isIndexLegal(index)) {
if (index < size / 2) {
DoubleNode node = head;
for (int i = 0; i < index; i++) {
node = node.next;
}
return node.val;
} else {
DoubleNode node = tail;
for (int i = size - 1; i >= index; i--) {
node = node.prev;
}
return node.val;
}
}
return -1;
}
public int setValueByIndex(int index, int newVal) {
DoubleNode node = null;
if (isIndexLegal(index)) {
if (index < size / 2) {
node = head;
for (int i = 0; i < index; i++) {
node = node.next;
}
node.val = newVal;
} else {
node = tail;
for (int i = size - 1; i >= index; i--) {
node = node.prev;
}
node.val = newVal;
}
}
return -1;
}
public void removeIndex(int index) {
if (index < 0 || index >= size) {
System.out.println("remove index illegal");
return;
}
DoubleNode cur = node(index);
unlink(cur);
}
public void removeFirst() {
removeIndex(0);
}
public void removeLast() {
removeIndex(size - 1);
}
public void removeValueByValue(int val) {
for (DoubleNode x = head; x != null; x = x.next) {
if (x.val == val) {
unlink(x);
break;
}
}
}
public void removeAllValue(int val) {
for (DoubleNode x = head; x != null; ) {
if (x.val == val) {
DoubleNode successor = x.next;
unlink(x);
x = successor;
} else {
x = x.next;
}
}
}
private void unlink(DoubleNode node) {
DoubleNode prev = node.prev;
DoubleNode successor = node.next;
//1.先处理node 的前半部分
if (prev == null) {
head = successor;
} else {
//前驱不为空的情况
prev.next = successor;
node.prev = null;
}
//2.再处理后半部分的情况
if (successor == null) {
tail = prev;
} else {
successor.prev = prev;
node.next = null;
}
size--;
}
//根据索引值找到对应的节点
private DoubleNode node(int index) {
DoubleNode x = null;
if (index < size / 2) {
x = head;
for (int i = 0; i < index; i++) {
x = x.next;
}
} else {
x = tail;
for (int i = size - 1; i > index; i--) {
x = x.prev;
}
}
return x;
}
public boolean isIndexLegal(int index) {
// if(index < 0 || index >= size){
// return false;
// }
// return true;
return !(index < 0 || index >= size);
}
public String toString() {
String ret = "";
for (DoubleNode x = head; x != null; x = x.next) {
ret += x.val;
ret += "->";
}
ret += "NULL";
return ret;
}
}
class DoubleNode {
DoubleNode prev;//前驱节点
int val;//当前节点值
DoubleNode next;//后继节点
public DoubleNode() {
}
public DoubleNode(int val) {
this.val = val;
}
public DoubleNode(DoubleNode prev, int val, DoubleNode next) {
this.prev = prev;
this.val = val;
this.next = next;
}
}
测试
带头单链表测试
package seqlist;
public class LinkedListWithHeadTest {
public static void main(String[] args) {
LinkedListWithHead linkedListWithHead = new LinkedListWithHead();
linkedListWithHead.addFirst(3);
linkedListWithHead.addFirst(2);
linkedListWithHead.addFirst(2);
linkedListWithHead.addFirst(3);
linkedListWithHead.addFirst(2);
// 2->2->2->2->3
System.out.println(linkedListWithHead);
linkedListWithHead.removeAllValue(2);
System.out.println(linkedListWithHead);
// System.out.println("----------------");
// System.out.println(linkedListWithHead.remove(0));
// System.out.println(linkedListWithHead.remove(1));
// System.out.println(linkedListWithHead);
}
}
双向链表测试
package seqlist;
public class DoubleLinkTest {
public static void main(String[] args) {
DoubleLinkedList doubleLinkedList = new DoubleLinkedList();
doubleLinkedList.addLast(1);
doubleLinkedList.addLast(3);
doubleLinkedList.addLast(3);
doubleLinkedList.addLast(2);
doubleLinkedList.addLast(3);
doubleLinkedList.removeValueByValue(3);
System.out.println(doubleLinkedList);
// doubleLinkedList.addLast(1);
// doubleLinkedList.addLast(3);
// doubleLinkedList.addLast(5);
// doubleLinkedList.add(1,2);
// doubleLinkedList.add(1,4);
//
// System.out.println(doubleLinkedList);
// doubleLinkedList.removeFirst();
// doubleLinkedList.removeLast();
// System.out.println(doubleLinkedList);
// System.out.println("---------------");
// doubleLinkedList.removeIndex(1);
// System.out.println(doubleLinkedList);
}
}
