什么是单向链表？
链表数据结构是线性数据结构，是真正意义上的动态数据结构，他不需要申请固定的内存空间，是通过代码层面来实现数据的逻辑关系。链表中有个变量名为head的Node节点，Node里面包含要存储的数据和下一个Node节点。
public class LinkedList<E> {
private Node<E> head;
private int size;
public LinkedList() {
}
private class Node<E> {
public E e;
public Node next;
public Node(E e, Node next) {
this.e = e;
this.next = next;
}
public Node(E e) {
this.e = e;
}
}
@Override
public String toString() {
StringBuffer stringBuffer = new StringBuffer();
stringBuffer.append("[");
Node<E> cur =head;
while(cur!=null){
stringBuffer.append(cur.e+",");
cur = cur.next;
}
stringBuffer.append("]");
return stringBuffer.toString();
}
添加元素，添加元素其实是找到要插入位置元素的前一个元素节点，然后把前一个Node节点的下一个Node添加到新创建的Node的下一个Node节点，然后再把新创建的节点设置给前一个节点的下一个节点，然后size++;
//指定位置添加元素
public void add(int index, E e) {
if (index < 0 || index > size) {
throw new IllegalArgumentException("index is error");
}
if (index == 0) {
Node<E> node = new Node<>(e, head);
head = node;
} else {
Node<E> pre = head;
for (int i = 0; i < index - 1; i++) {
pre = pre.next;
}
pre.next = new Node(e, pre.next);
}
size++;
}
public void addFirst(E e) {
add(0, e);
}
public void addLast(E e) {
add(size, e);
}
删除元素
public void removeFirst(){
head = head.next;
size--;
}
public void removeLast(){
removeIndex(size-1);
}
public void removeIndex(int index){
if(index==0){
removeFirst();
}else{
Node<E> pre = head;
for (int i = 0; i < index-1; i++) {
pre = pre.next;
}
pre.next = pre.next.next;
}
size--;
}
public void remove(E e) {
Node<E> curNode = head;
//如果表头存储的元素和e是一样的，就找下一个元素，直到表头存储的元素不在和e相等，执行后面while(curNode!=null)
while (curNode.e.equals(e)) {
curNode = curNode.next;
size--;
}
while (curNode != null) {
if (curNode.next.e.equals(e)) {
curNode.next = curNode.next.next;
size--;
} else {
curNode = curNode.next;
}
}
}
是否包含某个元素,非递归写法
public boolean contains(E e ){
Node<E> cur = head;
while(cur !=null){
if(cur.e.equals(e)){
return true;
}
cur = cur.next;
}
return false;
}
是否包含某个元素，递归写法,contains(E e)，是用户调用的方法，contains(Node<E> head,E e)是私有方法，内部调用。
public boolean contains(E e ){
return contains(head,e);
}
private boolean contains(Node<E> head, E e) {
if(head==null){
return false;
}
if(head.e.equals(e)){
return true;
}
return contains(head.next,e);
}
全部代码，以下是没有使用虚拟头结点来实现的单向链表。稍微有点复杂。
public class LinkedList<E> {
private Node<E> head;
private int size;
public LinkedList() {
}
private class Node<E> {
public E e;
public Node next;
public Node(E e, Node next) {
this.e = e;
this.next = next;
}
public Node(E e) {
this.e = e;
}
}
public void addFirst(E e) {
add(0, e);
}
public void addLast(E e) {
add(size, e);
}
public void add(int index, E e) {
if (index < 0 || index > size) {
throw new IllegalArgumentException("index is error");
}
if (index == 0) {
Node<E> node = new Node<>(e, head);
head = node;
} else {
Node<E> pre = head;
for (int i = 0; i < index - 1; i++) {
pre = pre.next;
}
pre.next = new Node(e, pre.next);
}
size++;
}
public boolean contains(E e ){
Node<E> cur = head;
while(cur !=null){
if(cur.e.equals(e)){
return true;
}
cur = cur.next;
}
return false;
}
//递归实现
// public boolean contains(E e ){
// return contains(head,e);
// }
//
// private boolean contains(Node<E> head, E e) {
//
// if(head==null){
// return false;
// }
// if(head.e.equals(e)){
// return true;
// }
// return contains(head.next,e);
// }
public void remove(E e) {
Node<E> curNode = head;
while (curNode.e.equals(e)) {
curNode = curNode.next;
size--;
}
while (curNode != null) {
if (curNode.next.e.equals(e)) {
curNode.next = curNode.next.next;
size--;
} else {
curNode = curNode.next;
}
}
}
public void removeFirst(){
head = head.next;
size--;
}
public void removeLast(){
removeIndex(size-1);
}
public void removeIndex(int index){
if(index==0){
removeFirst();
}else{
Node<E> pre = head;
for (int i = 0; i < index-1; i++) {
pre = pre.next;
}
pre.next = pre.next.next;
}
size--;
}
public int getSize() {
return size;
}
@Override
public String toString() {
StringBuffer stringBuffer = new StringBuffer();
stringBuffer.append("[");
Node<E> cur =head;
while(cur!=null){
stringBuffer.append(cur.e+",");
cur = cur.next;
}
stringBuffer.append("]");
return stringBuffer.toString();
}
}
使用虚拟头结点实现的单向链表
public class LinkedList2<E> {
private Node<E> dummyHead;
private int size;
public LinkedList2() {
dummyHead = new Node<E>();
}
private class Node<E> {
public E e;
public Node next;
public Node(E e, Node next) {
this.e = e;
this.next = next;
}
public Node(E e) {
this.e = e;
}
public Node() {
}
}
public void addFirst(E e) {
add(0, e);
}
public void addLast(E e) {
add(size, e);
}
public void add(int index, E e) {
if (index < 0 || index > size) {
throw new IllegalArgumentException("index is error");
}
Node<E> pre = dummyHead;
for (int i = 0; i < index; i++) {
pre = pre.next;
}
pre.next = new Node(e, pre.next);
size++;
}
public void remove(E e) {
Node<E> curNode = dummyHead.next;
while (curNode != null) {
if (curNode.next.e.equals(e)) {
curNode.next = curNode.next.next;
size--;
} else {
curNode = curNode.next;
}
}
}
public void removeFirst() {
removeIndex(0);
}
public void removeLast() {
removeIndex(size - 1);
}
public void removeIndex(int index) {
if (index < 0 || index >= size) {
throw new IllegalArgumentException("index 错误");
}
Node<E> pre = dummyHead;
for (int i = 0; i < index; i++) {
pre = pre.next;
}
pre.next = pre.next.next;
size--;
}
public boolean contains(E e) {
Node<E> cur = dummyHead.next;
while (cur != null) {
if(cur.e.equals(e)){
return true;
}
cur = cur.next;
}
return false;
}
public int getSize() {
return size;
}
@Override
public String toString() {
StringBuffer stringBuffer = new StringBuffer();
stringBuffer.append("[");
Node<E> cur = dummyHead.next;
while (cur != null) {
stringBuffer.append(cur.e + ",");
cur = cur.next;
}
stringBuffer.append("]");
return stringBuffer.toString();
}
}
网友评论